ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) 解题报告
分类:
IT文章
•
2022-04-15 13:56:54
A：A Serial Killer
![]()
1 #include <iostream>
2 //#include<bits/stdc++.h>
3 #include <stack>
4 #include <queue>
5 #include <map>
6 #include <set>
7 #include <cstdio>
8 #include <cstring>
9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 const int MAX=1e5+5;
15 //char a[15],b[15],c[15];
16 string a,b,c,d;
17 int n;
18 queue <pair<string,string> > que;
19 pair <string,string> x;
20 int main()
21 {
22 // scanf("%s %s",a,b);
23 cin>>a>>b;
24 // scanf("%d",&n);
25 cin>>n;
26 // que.push(make_pair(a,b));
27 // int i;
28 cout<<a<<" "<<b<<"
";
29 for(int i=1;i<=n;i++)
30 {
31 // scanf("%s",c);
32 cin>>c>>d;
33 if(a==c)
34 a=d;
35 else
36 b=d;
37 // if(strcmp(a,c)==0)
38 // strcpy(a,c);
39 // else
40 cout<<a<<" "<<b<<"
";
41 // strcpy(b,c);
42 }
43 // for(i=1;i<=n+1;i++)
44 // {
45 // x=que.front();
46 // que.pop();
47 //// printf("%s %s
".x.first,x.second);
48 // cout<<x.first<<" "<<x.second<<"
";
49 // }
50
51 }
View Code
B：Sherlock and his girlfriend
![]()
1 #include <iostream>
2 //#include<bits/stdc++.h>
3 #include <stack>
4 #include <queue>
5 #include <map>
6 #include <set>
7 #include <cstdio>
8 #include <cstring>
9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 const int MAX=1e5+5;
15 bool vi[MAX];
16 int prime[MAX],n;
17 void getprime()
18 {
19 memset(vi,false,sizeof(vi));
20 int num=0;
21 for(int i=2;i<=n+2;++i)
22 {
23 if(!vi[i])
24 prime[++num]=i;
25 for(int j=1;j<=num&&i*prime[j]<=n+2;j++)
26 {
27 vi[i*prime[j]]=true;
28 if(i%prime[j]==0)
29 break;
30 }
31 }
32 }
33 int main()
34 {
35 scanf("%d",&n);
36 if(n<=2)
37 {
38 if(n==1)
39 printf("1
1
");
40 else
41 printf("1
1 1
");
42 return 0;
43 }
44 else
45 {
46 getprime();
47 printf("2
");
48 for(int i=2;i<=n+1;i++)
49 {
50 // printf("%d",i);
51 if(vi[i])
52 printf("2 ");
53 else
54 printf("1 ");
55 }
56 }
57 }
View Code
C：Molly's Chemicals
不用n^2 把所有区间和都求出来，10^10必然会超时，只需要每次把可能的求出就行了！！！（只能怪自己太蠢）
![]()
1 #include <iostream>
2 //#include<bits/stdc++.h>
3 #include <stack>
4 #include <queue>
5 #include <map>
6 #include <set>
7 #include <cstdio>
8 #include <cstring>
9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 const int MAX=1e5+5;
15 const ll da=1e14+5;
16 ll mi[1000];
17 map <ll ,ll > x;
18 ll tem=0LL,he=0LL;
19 ll an=0;
20 ll cnt=0;
21 int main()
22 {
23 int n,k;
24 cin>>n>>k;
25 mi[0]=1;
26 cnt=1;
27 int i;
28 if(k==-1)
29 {
30 mi[1]=-1;cnt=2;
31 }
32 else if(k!=1)
33 {
34
35 for(i=1;mi[i-1]<da;i++)
36 {
37 mi[i]=mi[i-1]*k;
38 }
39 cnt=i;
40 }
41 x[0]++;
42 for(i=1;i<=n;i++)
43 {
44 cin>>tem;
45 he+=tem;
46 // cout<<he<<"
";
47 x[he]++;
48 for(int j=0;j<cnt;j++)
49 an+=x[he-mi[j]];
50 }
51 cout<<an<<"
";
52 }
53 /*
54 10 1
55 -1 1 -1 1 -1 1 -1 1 -1 1
56 */
View Code
如官方题解所述，将房间视为边，开关视为定点。（每个房间恰由2个开关控制，恰好为边的两个顶点）接下来就变成了染色问题。初始关门的，左右两个顶点颜色不同（因为需要改变这个房间状态，可认为不操作是1种颜色，操作1次是另一种颜色）；初始开门的，左右两个颜色相同。从第一个点开始染色，如果最后能全顺利染完就YES，不然就NO
![]()
1 #include <iostream>
2 //#include<bits/stdc++.h>
3 #include <stack>
4 #include <queue>
5 #include <map>
6 #include <set>
7 #include <cstdio>
8 #include <cstring>
9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 const int MAX=1e5+5;
15 struct bian
16 {
17 int l,r;
18 int num;
19 }edge[MAX];
20 bool vi[MAX];
21 vector <pair <int,int> > link[MAX];
22 queue <int> que;
23 int node[MAX];//顶点的状态
24 int n,m;
25 bool bfs()
26 {
27 memset(vi,false,sizeof(vi));
28 memset(node,-1,sizeof(node));
29 int s,i;
30 int st,nxt;//边的颜色，边的另一个顶点
31 for(i=1;i<=m;i++)
32 {
33 if(node[i]==-1)
34 {
35 que.push(i);
36 node[i]=1;
37 }
38 while(!que.empty())
39 {
40 i=que.front();
41 que.pop();
42 for(s=0;s<link[i].size();s++)
43 {
44 st=link[i][s].first;
45 nxt=link[i][s].second;
46 if(node[nxt]==-1)
47 {
48 if(st==0)
49 {
50 node[nxt]=(node[i]?0:1);
51 }
52 else
53 node[nxt]=(node[i]?1:0);
54 que.push(nxt);
55 }
56 else
57 {
58 if(st==0)
59 {
60 if(node[nxt]==node[i])
61 return false;
62 }
63 else
64 if(node[nxt]!=node[i])
65 return false;
66 }
67 }
68 }
69 }
70 return true;
71 }
72
73 int main()
74 {
75 scanf("%d %d",&n,&m);
76 int i;
77 for(i=1;i<=n;i++)
78 {
79 scanf("%d",&edge[i].num);
80 edge[i].l=edge[i].r=0;
81 }
82 int ge,tem;
83 for(i=1;i<=m;i++)
84 {
85 scanf("%d",&ge);
86 for(int j=1;j<=ge;j++)
87 {
88 scanf("%d",&tem);//读入与这个结点相连的边的编号
89 if(edge[tem].l!=0)
90 edge[tem].r=i;
91 else
92 edge[tem].l=i;
93 }
94 }
95 for(i=1;i<=n;i++)
96 {
97 int zuo,you;
98 zuo=edge[i].l;
99 you=edge[i].r;
100 link[zuo].push_back(pair<int,int>(edge[i].num,you));
101 link[you].push_back(pair<int,int>(edge[i].num,zuo));
102 }
103 if(bfs())
104 printf("YES
");
105 else
106 printf("NO
");
107 }
