Day 1

https://www.luogu.org/problem/show?pid=3719

solution：　　

　　题目剧毒吧，注意读入（写挂n次）。

　　模拟。

 1 #include<cstdio>
 2 #define Max(a,b) (a>b?a:b)
 3 using namespace std;
 4 int cxsb(){
 5     int maxx=0,cnt=0;
 6     while(1){
 7         char ch=getchar();
 8         switch(ch){
 9             case 'a':{cnt++;break;}
10             case '(':{cnt+=cxsb();break;}
11             case ')':{maxx=Max(maxx,cnt);return maxx;}
12             case '|':{maxx=Max(maxx,cnt);cnt=0;break;}
13             default :{maxx=Max(maxx,cnt);return maxx;}
14         }
15     }
16 }
17 int main(){
18     printf("%d",cxsb());
19     return 0;
20 }

3719

https://www.luogu.org/problem/show?pid=2037

solution：　　

　　打表模拟。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define MN 100005
 5 using namespace std;
 6 const int f[25]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9};
 7 string s[MN];bool flag;int num=0,n;
 8 inline void check(int cnt){
 9     string sa;cin>>sa;int len=sa.length();
10     for(int i=0;i<len;i++){
11         if(sa[i]<='9'&&sa[i]>='0') s[cnt]+=sa[i];
12         else if(sa[i]>='A'&&sa[i]<='Z') s[cnt]+=f[sa[i]-'A']+'0';
13     }
14 }
15 inline void out(){
16     for(int i=1;i<=n+1;i++){
17         if(s[i]!=s[i-1]) {if(num>1) cout<<s[i-1].substr(0,3)<<'-'<<s[i-1].substr(3,4)<<' '<<num<<endl,flag=true;num=1;}
18         else num++;
19     }
20 }
21 int main(){
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++)check(i);
24     sort(s+1,s+n+1);
25     out();if(!flag) printf("No duplicates.
");
26 }

2037

Day2：

https://www.luogu.org/problem/show?pid=1160

solution：

　　双向链表。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 100005
 4 using namespace std;
 5 int n;
 6 bool visited[MAXN]; 
 7 struct queue{
 8     int l,r,id;
 9 }q[MAXN];
10 int main(){
11     scanf("%d",&n);
12     q[1]=(queue){0,0,1};
13     for(int i=2;i<=n;i++){
14         int k,p;scanf("%d%d",&k,&p);
15         if(p==0){
16             q[i].l=q[k].l,q[i].r=k;
17             q[q[i].l].r=i;
18             q[q[i].r].l=i;
19         }else{
20             q[i].l=k,q[i].r=q[k].r;
21             q[q[i].l].r=i;
22             q[q[i].r].l=i;
23         }
24         q[i].id=i;
25     }
26     int m;scanf("%d",&m);
27     memset(visited,0,sizeof(visited));
28     while(m--){
29         int x;scanf("%d",&x);
30         if(visited[x]) continue ;
31         q[q[x].l].r=q[x].r;
32         q[q[x].r].l=q[x].l;
33         visited[x]=true;
34     }
35     int now=q[0].r;
36     while(now!=0) {
37         printf("%d ",q[now].id);
38         now=q[now].r;
39     }
40     return 0;
41 }

1160

https://www.luogu.org/problem/show?pid=2085

solution：

　　每个函数在定义域内单调递增，我们可以建一个小根堆来模拟。

 1 #include<cstdio>
 2 #include<queue>
 3 #define MAXN 10005
 4 using namespace std;
 5 int n,m;
 6 int a[MAXN],b[MAXN],c[MAXN],F[MAXN][MAXN];
 7 priority_queue <int,vector<int>,greater<int> > q;
 8 int main(){
 9     scanf("%d%d",&n,&m);
10     for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
11     int cnt=0;
12     for(int j=1;j<=n;j++){
13         cnt++;
14         for(int k=1;k<=100;k++) {
15             F[j][k]=a[cnt]*k*k+b[cnt]*k+c[cnt];
16             q.push(F[j][k]);
17         }
18     }
19     for(int i=1;i<=m;i++){
20         int top=q.top();
21         q.pop();printf("%d ",top);
22     }
23     return 0;
24 }

2085

 1 #include <queue>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 const int maxn=10000+15;
 9 int n,m;
10 int a[maxn],b[maxn],c[maxn];
11 struct Node
12 {
13     int key,x,y;
14     Node(int key=0,int x=0,int y=0):key(key),x(x),y(y) {}
15 };
16 const bool operator < (const Node &a,const Node &b)
17 {
18     return a.key>b.key;
19 }
20 priority_queue <Node> que;
21 int f(int x,int y)
22 {
23     return a[x]*y*y+b[x]*y+c[x];
24 }
25 int main()
26 {
27     scanf("%d%d",&n,&m);
28     for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
29     for (int i=1;i<=n;i++) que.push(Node(f(i,1),i,1));
30     for (int i=1;i<=m;i++)
31     {
32         Node now=que.top();
33         if (i<m) printf("%d ",now.key);
34          else printf("%d
",now.key);
35         que.pop();
36         que.push(Node(f(now.x,now.y+1),now.x,now.y+1));
37     }
38     return 0;
39 }

2085//

https://www.luogu.org/problem/show?pid=3045

solution：

　　贪心+堆。

　　考虑买下前k个打折后最便宜的牛，如果买不下可以直接break。如果买的下，就考虑剩下的每一头牛i，要么是pi买入，要么是打折后的牛j，以pj-cj+ci买入。

　　一边不断贪心一边用三个堆维护。

 1 #include<queue>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define MAXN 50005
 5 #define LL long long
 6 using namespace std;
 7 int n,k,cnt=0;LL m;
 8 bool vis[MAXN];
 9 struct Node{
10     int x;LL n;
11     Node(LL a,int b) {n=a,x=b;};
12     bool operator < (const Node &a) const{return n>a.n;};
13 };
14 priority_queue<Node> p,c;
15 priority_queue<LL,vector<LL>,greater<LL> > p_c;
16 LL pp[MAXN],cc[MAXN];
17 int main(){
18     scanf("%d%d%d",&n,&k,&m);
19     for(int i=1;i<=n;i++) {
20         scanf("%d%d",&pp[i],&cc[i]);
21         p.push(Node(pp[i],i));c.push(Node(cc[i],i));
22     }
23     for(int i=1;i<=k;i++) p_c.push(0LL);
24     while(m>0&&cnt<n){
25         while(vis[p.top().x]) p.pop();
26         while(vis[c.top().x]) c.pop();
27         if(p_c.top()+c.top().n<p.top().n){
28             Node t=c.top();
29             LL x=p_c.top()+t.n;
30             if(m<x) break;
31             m-=x;p_c.pop();
32             p_c.push(pp[t.x]-cc[t.x]);
33             vis[t.x]=1;
34         }
35         else{
36             Node t=p.top();
37             LL x=t.n;
38             if(m<x) break;
39             m-=x;
40             vis[t.x]=1;
41         }
42         cnt++; 
43     }
44     printf("%d",cnt);
45     return 0;
46 }

3045

https://www.luogu.org/problem/show?pid=1955

solution：

　　并查集。

　　把所有条件都都进来，然后所有等于条件的作为边然后判断连通性。

　　之后在对所有的不等式判断是不是属于同一个联通块。

　　（在大牛模式下过的，主站T了第二个点）所以应该不是最优解。

 1 #include<map>
 2 #include<cstdio>
 3 #define MAXN 200005
 4 using namespace std;
 5 int t,n;
 6 int rank[MAXN],fa[MAXN],tot=0;
 7 int ii[MAXN],jj[MAXN];
 8 map <int,int> Map;
 9 int find(int x){
10     if(fa[x]==x) return x;
11     return fa[x]=find(fa[x]);
12 }
13 void merge(int x,int y){
14     int fx=find(x),fy=find(y);
15     if(fx==fy) return ;
16     if(rank[fx]==rank[fy]) rank[fx]++;
17     if(rank[fx]>rank[fy])  fa[fy]=fx;
18     else fa[fx]=fy;
19     return;
20 }
21 int main(){
22     scanf("%d",&t);
23     while(t--){
24         scanf("%d",&n);
25         Map.clear();
26         tot=0;
27         int sg=0;
28         while(n--){
29             int i,j,e;scanf("%d%d%d",&i,&j,&e);
30             if(Map.find(i)==Map.end()){
31                 tot++;Map[i]=tot;
32                 rank[tot]=0;fa[tot]=tot;
33             }
34             if(Map.find(j)==Map.end()){
35                 tot++;Map[j]=tot;
36                 rank[tot]=0;fa[tot]=tot;
37             }
38             i=Map[i];j=Map[j];
39             if(e==1) merge(i,j);
40             else sg++,ii[sg]=i,jj[sg]=j;
41         }
42         bool boo=true;
43         for(int i=1;i<=sg;i++) if(find(ii[i])==find(jj[i])) boo=false;
44         if(boo) printf("YES
");
45         else printf("NO
");
46     }
47     return 0;
48 }

1955

　Updata：

　　常数太大了。在zxyer的帮助下A惹。

 1 #include<cstdio>
 2 #include <algorithm>
 3 #define MAXN 200005
 4 using namespace std;
 5 int t,n;
 6 int rank[MAXN],fa[MAXN],tot=0,id[MAXN<<1],vn;
 7 struct queries{
 8     int x,y,opt;
 9 }q[MAXN];
10 int find(int x){
11     if(fa[x]==x) return x;
12     return fa[x]=find(fa[x]);
13 }
14 void merge(int x,int y){
15     int fx=find(x),fy=find(y);
16     if(fx==fy) return ;
17     if(rank[fx]==rank[fy]) rank[fx]++;
18     if(rank[fx]>rank[fy])  fa[fy]=fx;
19     else fa[fx]=fy;
20     return;
21 }
22 int main(){
23     scanf("%d",&t);
24     while(t--){
25         scanf("%d",&n);
26         tot=0;
27         int sg=0;
28         for (int i=1; i<=n; ++i){
29             scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].opt);
30             id[i-1<<1]=q[i].x,id[i-1<<1|1]=q[i].y;    
31         }sort(id,id+(n<<1));vn=unique(id,id+(n<<1))-id-1;
32         for (int i=0; i<=vn; ++i) fa[i]=i;
33         for (int i=1; i<=n; ++i){
34             q[i].x=lower_bound(id,id+vn,q[i].x)-id,q[i].y=lower_bound(id,id+vn,q[i].y)-id;
35             if (q[i].opt==1) merge(q[i].x,q[i].y);
36         }
37         bool boo=true;
38         for(int i=1;i<=n;i++) if(q[i].opt==0&&find(q[i].x)==find(q[i].y)) boo=false;
39         if(boo) printf("YES
");
40         else printf("NO
");
41     }
42     return 0;
43 }

1955

https://www.luogu.org/problemnew/show/2342

solution：

　　并查集。

　　路径压缩的时候要记录一个root。（挂到心累...）

 1 #include<cstdio>
 2 #include<iostream>
 3 #define MAXN 30005
 4 using namespace std;
 5 int p,a,b;
 6 char ch;
 7 int fa[MAXN],sum[MAXN],fro[MAXN],rank[MAXN];
 8 inline int Abs(int x){return x>0?x:-x;}
 9 inline int find(int x){
10     if(x==fa[x]) return fa[x];
11     else {
12         int root=find(fa[x]);
13         fro[x]+=fro[fa[x]];
14         return fa[x]=root;
15     }
16 }
17 inline void merge(int x,int y){
18     int fx=find(x),fy=find(y);
19     if(fx==fy) return ;
20     fa[fx]=fy;
21     fro[fx]+=sum[fy];
22     sum[fy]+=sum[fx];
23     find(x),find(y);
24 }
25 inline int check(int x,int y){
26     if(find(x)!=find(y)) return -1;
27     return Abs(fro[x]-fro[y]);
28 }
29 int main(){
30     for(int i=1;i<=MAXN;i++) fa[i]=i,sum[i]=1,fro[i]=0;
31     cin>>p;
32     for(int i=1;i<=p;i++){
33         char ch;cin>>ch;
34         if(ch=='M') {
35             int x,y;scanf("%d%d",&x,&y);
36             merge(x,y);
37         }    
38         else if(ch=='C') {
39             int x;scanf("%d",&x);
40             printf("%d
",check(x,find(x)));
41         } 
42     }
43     return 0; 
44 }

2342

https://www.luogu.org/problemnew/show/1196

solution：

　　并查集。

　　和2342一模一样。

 1 #include<cstdio>
 2 #include<iostream>
 3 #define MAXN 30005
 4 using namespace std;
 5 int p,a,b;
 6 char ch;
 7 int fa[MAXN],sum[MAXN],fro[MAXN],rank[MAXN];
 8 inline int Abs(int x){return x>0?x:-x;}
 9 inline int find(int x){
10     if(x==fa[x]) return fa[x];
11     else {
12         int root=find(fa[x]);
13         fro[x]+=fro[fa[x]];
14         return fa[x]=root;
15     }
16 }
17 inline void merge(int x,int y){
18     int fx=find(x),fy=find(y);
19     if(fx==fy) return ;
20     fa[fx]=fy;
21     fro[fx]+=sum[fy];
22     sum[fy]+=sum[fx];
23     //find(x),find(y);
24 }
25 inline int check(int x,int y){
26     if(find(x)!=find(y)) return -1;
27     return Abs(fro[x]-fro[y])-1;
28 }
29 int main(){
30     for(int i=1;i<=MAXN;i++) fa[i]=i,sum[i]=1,fro[i]=0;
31     cin>>p;
32     for(int i=1;i<=p;i++){
33         char ch;cin>>ch;
34         if(ch=='M') {
35             int x,y;scanf("%d%d",&x,&y);
36             merge(x,y);
37         }    
38         else if(ch=='C') {
39             int x,y;scanf("%d%d",&x,&y);
40             printf("%d
",check(x,y));
41         } 
42     }
43     return 0; 
44 }

1196