开启辅助访问
 找回密码
 注册帐号

扫一扫,访问微社区

首页   >   博客   >   水云oFl18

little susie Codeforces Round #303 (Div. 2)

个人分类: ACM比赛 | 2017-1-12 17:36
0 个评论 | 阅读 68 | 收藏 | 举报

little susie


一个水题+4个贪心....
Codeforces Round #303 (Div. 2) A. Toy Cars time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Little Susie, thanks to her older brother, likes to play with cars. Today she decided to set up a tournament between them. The process of a tournament is described in the next paragraph. There are n toy cars. Each pair collides. The result of a collision can be one of the following: no car turned over, one car turned over, both cars turned over. A car is good if it turned over in no collision. The results of the collisions are determined by an n × n matrix А: there is a number on the intersection of the і-th row and j-th column that describes the result of the collision of the і-th and the j-th car:
  •  - 1: if this pair of cars never collided.  - 1 occurs only on the main diagonal of the matrix.
  • 0: if no car turned over during the collision.
  • 1: if only the i-th car turned over during the collision.
  • 2: if only the j-th car turned over during the collision.
  • 3: if both cars turned over during the collision.
Susie wants to find all the good cars. She quickly determined which cars are good. Can you cope with the task? Input The first line contains integer n (1 ≤ n ≤ 100) — the number of cars. Each of the next n lines contains n space-separated integers that determine matrix A. It is guaranteed that on the main diagonal there are  - 1, and  - 1 doesn't appear anywhere else in the matrix. It is guaranteed that the input is correct, that is, if Aij = 1, then Aji = 2, if Aij = 3, then Aji = 3, and if Aij = 0, then Aji = 0. Output Print the number of good cars and in the next line print their space-separated indices in the increasing order. Sample test(s) input 3 -1 0 0 0 -1 1 0 2 -1 output 2 1 3 input 4 -1 3 3 3 3 -1 3 3 3 3 -1 3 3 3 3 -1 output 0 /* *********************************************** Author :CKboss Created Time :2015年05月20日 星期三 00时23分11秒 File Name :A.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; const int maxn=111; int n; int mat[maxn][maxn]; vector<int> vi; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { bool flag=true; for(int j=1;j<=n;j++) { scanf("%d",&mat[i][j]); if(mat[i][j]==1||mat[i][j]==3) flag=false; } if(flag) vi.push_back(i); } int sz=vi.size(); printf("%d\n",sz); for(int i=0;i<sz;i++) printf("%d ",vi[i]); return 0; }


B. Equidistant String time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance: We will define the distance between two strings s and t of the same length consisting of digits zero and one as the number of positions i, such that siisn't equal to ti. As besides everything else Susie loves symmetry, she wants to find for two strings s and t of length n such string p of length n, that the distance fromp to s was equal to the distance from p to t. It's time for Susie to go to bed, help her find such string p or state that it is impossible. Input The first line contains string s of length n. The second line contains string t of length n. The length of string n is within range from 1 to 105. It is guaranteed that both strings contain only digits zero and one. Output Print a string of length n, consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line "impossible" (without the quotes). If there are multiple possible answers, print any of them. Sample test(s) input 0001 1011 output 0011 input 000 111 output impossible Note In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101. 分情况讨论: /* *********************************************** Author :CKboss Created Time :2015年05月20日 星期三 00时35分51秒 File Name :B.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; const int maxn=1001000; int n; char s[maxn]; char t[maxn]; char p[maxn]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%s",s); scanf("%s",t); int n=strlen(s); int diff01=0,diff10=0; for(int i=0;i<n;i++) { if(s[i]!=t[i]) { if(s[i]=='0'&&t[i]=='1') diff01++; else diff10++; } else p[i]=s[i]; } if(diff01%2==0&&diff10%2==0) { for(int i=0;i<n;i++) { if(s[i]!=t[i]) { if(s[i]=='0'&&t[i]=='1') { if(diff01%2==0) p[i]='0'; else p[i]='1'; diff01--; } else { if(diff10%2==0) p[i]='0'; else p[i]='1'; diff10--; } } } } if((diff01%2==0&&diff10%2==1)||(diff01%2==1&&diff10%2==0)) { puts("impossible"); return 0; } else { int s10=1,s01=1; for(int i=0;i<n;i++) { if(s[i]!=t[i]) { if(s[i]=='0') { if(s01==1) p[i]='1'; else p[i]='0'; s01=1-s01; } else { if(s10==1) p[i]='1'; else p[i]='0'; s10=1-s10; } } } } printf("%s\n",p); return 0; }

C. Woodcutters time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood. She imagined the situation that is described below. There are n trees located along the road at points with coordinates x1, x2, ..., xn. Each tree has its height hi. Woodcutters can cut down a tree and fell it to the left or to the right. After that it occupies one of the segments [xi - hi, xi] or [xi;xi + hi]. The tree that is not cut down occupies a single point with coordinate xi. Woodcutters can fell a tree if the segment to be occupied by the fallen tree doesn't contain any occupied point. The woodcutters want to process as many trees as possible, so Susie wonders, what is the maximum number of trees to fell. Input The first line contains integer n (1 ≤ n ≤ 105) — the number of trees. Next n lines contain pairs of integers xi, hi (1 ≤ xi, hi ≤ 109) — the coordinate and the height of the і-th tree. The pairs are given in the order of ascending xi. No two trees are located at the point with the same coordinate. Output Print a single number — the maximum number of trees that you can cut down by the given rules. Sample test(s) input 5 1 2 2 1 5 10 10 9 19 1 output 3 input 5 1 2 2 1 5 10 10 9 20 1 output 4 Note In the first sample you can fell the trees like that:
  • fell the 1-st tree to the left — now it occupies segment [ - 1;1]
  • fell the 2-nd tree to the right — now it occupies segment [2;3]
  • leave the 3-rd tree — it occupies point 5
  • leave the 4-th tree — it occupies point 10
  • fell the 5-th tree to the right — now it occupies segment [19;20]
In the second sample you can also fell 4-th tree to the right, after that it will occupy segment [10;19]. 贪心,尽量往左边倒,如果不行往右边倒(也不会影响最优值) /* *********************************************** Author :CKboss Created Time :2015年05月20日 星期三 01时52分14秒 File Name :C.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; const int maxn=100100; int n; struct Tree { int x,h; }tree[maxn]; bool cmp(Tree a,Tree b) { if(a.x!=b.x) return a.x<b.x; return a.h<b.h; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); for(int i=0,x,h;i<n;i++) { scanf("%d%d",&x,&h); tree[i].x=x; tree[i].h=h; } sort(tree,tree+n,cmp); if(n==1||n==2) { printf("%d\n",n); return 0; } int kan=2; int ToLeft=tree[1].x-tree[0].x; for(int i=1;i<n-1;i++) { int left=tree[i].x-tree[i].h; int right=tree[i].x+tree[i].h; if(tree[i].h<ToLeft) { /// 往左边倒 kan++; ToLeft=tree[i+1].x-tree[i].x; } else if(right<tree[i+1].x) { kan++; ToLeft=tree[i+1].x-tree[i].x-tree[i].h; } else /// cant { ToLeft=tree[i+1].x-tree[i].x; } } printf("%d\n",kan); return 0; }

D. Queue time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Little girl Susie went shopping with her mom and she wondered how to improve service quality. There are n people in the queue. For each person we know time ti needed to serve him. A person will be disappointed if the time he waits is more than the time needed to serve him. The time a person waits is the total time when all the people who stand in the queue in front of him are served. Susie thought that if we swap some people in the queue, then we can decrease the number of people who are disappointed. Help Susie find out what is the maximum number of not disappointed people can be achieved by swapping people in the queue. Input The first line contains integer n (1 ≤ n ≤ 105). The next line contains n integers ti (1 ≤ ti ≤ 109), separated by spaces. Output Print a single number — the maximum number of not disappointed people in the queue. Sample test(s) input 5 15 2 1 5 3 output 4 Note Value 4 is achieved at such an arrangement, for example: 1, 2, 3, 5, 15. Thus, you can make everything feel not disappointed except for the person with time 5.
贪心: 从小到大排序,遇到已经angry的就跳过 /* *********************************************** Author :CKboss Created Time :2015年05月20日 星期三 01时23分17秒 File Name :D.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long int LL; int n; LL t[100100]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); for(int i=0;i<n;i++) cin>>t[i]; sort(t,t+n); LL total=0; int allright=0; for(int i=0;i<n;i++) { if(total<t[i]) { allright++; total+=t[i]; } else if(total>=t[i]) { continue; } } int angry=0; total=0; for(int i=0;i<n;i++) { if(total>t[i]) angry++; else total+=t[i]; } printf("%d\n",max(allright,n-angry)); return 0; }

E. Paths and Trees time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output Little girl Susie accidentally found her elder brother's notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to ask you about it. So, the problem statement is as follows. Let's assume that we are given a connected weighted undirected graph G = (V, E) (here V is the set of vertices, E is the set of edges). The shortest-path tree from vertex u is such graph G1 = (V, E1) that is a tree with the set of edges E1 that is the subset of the set of edges of the initial graph E, and the lengths of the shortest paths from u to any vertex to G and to G1 are the same. You are given a connected weighted undirected graph G and vertex u. Your task is to find the shortest-path tree of the given graph from vertex u, the total weight of whose edges is minimum possible. Input The first line contains two numbers, n and m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of vertices and edges of the graph, respectively. Next m lines contain three integers each, representing an edge — ui, vi, wi — the numbers of vertices connected by an edge and the weight of the edge (ui ≠ vi, 1 ≤ wi ≤ 109). It is guaranteed that graph is connected and that there is no more than one edge between any pair of vertices. The last line of the input contains integer u (1 ≤ u ≤ n) — the number of the start vertex. Output In the first line print the minimum total weight of the edges of the tree. In the next line print the indices of the edges that are included in the tree, separated by spaces. The edges are numbered starting from 1 in the order they follow in the input. You may print the numbers of the edges in any order. If there are multiple answers, print any of them. Sample test(s) input 3 3 1 2 1 2 3 1 1 3 2 3 output 2 1 2 input 4 4 1 2 1 2 3 1 3 4 1 4 1 2 4 output 4 2 3 4 Note In the first sample there are two possible shortest path trees:
  • with edges 1 – 3 and 2 – 3 (the total weight is 3);
  • with edges 1 – 2 and 2 – 3 (the total weight is 2);
And, for example, a tree with edges 1 – 2 and 1 – 3 won't be a shortest path tree for vertex 3, because the distance from vertex 3 to vertex 2 in this tree equals 3, and in the original graph it is 1.
贪心: Dijkstra 加边的时候加尽量小的边
/* *********************************************** Author :CKboss Created Time :2015年05月20日 星期三 15时48分59秒 File Name :E2.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long int LL; typedef pair<LL,LL> pII; const LL maxn=300300; const LL INF=0x3f3f3f3f3f3f3f3f; LL n,m,S; struct Edge { LL to,next,len,id; }edge[maxn*2]; LL Adj[maxn],Size; void init() { memset(Adj,-1,sizeof(Adj)); Size=0; } void Add_Edge(LL u,LL v,LL len,LL id) { edge[Size].to=v; edge[Size].len=len; edge[Size].id=id; edge[Size].next=Adj[u]; Adj[u]=Size++; } LL dist[maxn]; bool vis[maxn]; LL ex[maxn]; LL pre[maxn]; void dijkstra() { memset(dist,63,sizeof(dist)); memset(ex,63,sizeof(ex)); dist[S]=0; ex[S]=0; priority_queue<pII> q; /// -距离,点 q.push(make_pair(0,S)); while(!q.empty()) { pII tp=q.top(); q.pop(); LL u=tp.second; if(vis[u]==true) continue; vis[u]=true; for(LL i=Adj[u];~i;i=edge[i].next) { LL v=edge[i].to; LL len=edge[i].len; LL id=edge[i].id; if(vis[v]) continue; if(dist[v]>dist[u]+len) { dist[v]=dist[u]+len; pre[v]=id; ex[v]=len; q.push(make_pair(-dist[v],v)); } else if(dist[v]==dist[u]+len&&ex[v]>len) { pre[v]=id; ex[v]=len; } } } LL all=0; memset(vis,0,sizeof(vis)); vector<LL> ve; for(LL i=1;i<=n;i++) { if(ex[i]!=INF) all+=ex[i]; if(i!=S) ve.push_back(pre[i]); } printf("%I64d\n",all); sort(ve.begin(),ve.end()); unique(ve.begin(),ve.end()); for(int i=0,sz=ve.size();i<sz;i++) cout<<ve[i]<<" "; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); init(); scanf("%I64d%I64d",&n,&m); for(LL i=0,x,y,z;i<m;i++) { scanf("%I64d%I64d%I64d",&x,&y,&z); Add_Edge(x,y,z,i+1); Add_Edge(y,x,z,i+1); } scanf("%I64d",&S); dijkstra(); return 0; }






转自:点击查看

0 0

评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册帐号

个人分类

标签

阅读排行

评论排行

推荐博客

最新博客

返回顶部