“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学)

题目链接传送门

官方题解传送门

I签到就完事了。

 1 #include<cstdio>
 2 int main()
 3 {
 4     int n,a,b,c,d,x,sum=0;
 5     scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
 6     while(n--)
 7     {
 8         scanf("%d",&x);
 9         sum+=x;
10     }
11     int ans1=sum,ans2=sum;
12     if(sum>=a)
13         ans1-=b;
14     if(sum>=c)
15         ans2-=d;
16     if(ans1<=ans2)
17         printf("%d
",ans1);
18     else
19         printf("%d
",ans2);
20     return 0;
21 }

日常签到

B题就模拟，枚举底边两个点，然后根据宽度差去找上面的或者下面那个顶点，然后去重。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std; 
 4 char a[118][118];
 5 bool vis[28][28][28];
 6 int main()
 7 {
 8     int n;
 9     scanf("%d",&n);
10     for(int i=0;i<=n;i++)
11         scanf("%s",a[i]);
12     int ans=0;
13     for(int i=0;i<=n;i++)
14     {
15         for(int j=0;j<i;j++)
16         {
17             for(int k=j+1;k<=i;k++)
18             {
19                 char s[5];
20                 if(i-(k-j)>=0&&i-(k-j)>=j)
21                 {
22                     s[0]=a[i][j];
23                     s[1]=a[i][k];
24                     s[2]=a[i-(k-j)][j];
25                     sort(s,s+3);
26                     if(!vis[s[0]-'a'][s[1]-'a'][s[2]-'a'])
27                     {
28                         vis[s[0]-'a'][s[1]-'a'][s[2]-'a']=1;
29                         ans++;
30                     }
31                 }
32                 if(i+(k-j)<=n&&i+(k-j)>=j+(k-j))
33                 {
34                     s[0]=a[i][j];
35                     s[1]=a[i][k];
36                     s[2]=a[i+(k-j)][j+(k-j)];
37                     sort(s,s+3);
38                     if(!vis[s[0]-'a'][s[1]-'a'][s[2]-'a'])
39                     {
40                         vis[s[0]-'a'][s[1]-'a'][s[2]-'a']=1;
41                         ans++;
42                     }
43                 }
44             }
45         }
46     }
47     printf("%d
",ans);
48     return 0;
49 }

模拟

A题思维题，一开始没想到，写完B题后看那么多人过了，模拟下，就是把前缀是它的后缀的放在它后面，所以答案就是区间子串的数目。

 1 #include<cstdio>
 2 char s[11108];
 3 int main()
 4 {
 5     int n,q,l,r;
 6     scanf("%d%d",&n,&q);
 7     scanf("%s",s);
 8     while(q--)
 9     {
10         scanf("%d%d",&l,&r);
11         printf("%d
",(r-l+1)*(r-l+2)/2);
12     }
13     return 0;
14 }

思维

D题博弈，首先对某一堆石子来说，如果它只有一个石子，没得选择，而如果是石子数>1的话，那么就可以全部拿完，或者只剩一个来调整自己是先手还是后手，因为两人都足够聪明，所以我是可以知道最后是先手还是后手赢的。那就是第一个遇到某堆石子数大于1的那个人，他可以控制自己的状态，所以他必胜。然后就是需要也特判一下全是1的情况。（还有wjytxdy）

 1 //wjytxdy 
 2 #include<cstdio>
 3 const int N=100118;
 4 int a[N],ans[N];
 5 int main()
 6 {
 7     int n,flag=0;
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++)
10     {
11         scanf("%d",&a[i]);
12         if(a[i]>1)
13             flag=1;
14         ans[i]=-1;
15     }
16     if(!flag)//全1特判 
17     {
18         for(int i=1;i<=n;i++)
19             if(n&1)
20                 printf("First
");
21             else
22                 printf("Second
");
23         return 0;
24     }
25     for(int i=1,j;i<=n;i++)
26     {
27         if(ans[i]!=-1)//已经知道这个位置是必胜还是必败了就跳过 
28             continue;
29         j=i;
30         do{
31             if(a[j]>1)
32                 break;
33             j++;
34             if(j>n)
35                 j-=n; 
36         }while(j!=i);//找第一个石子数大于1的堆 
37         if(j<i)//j在i前面说明绕回来了 
38             j+=n;
39         for(int k=i;k<=j;k++)//两堆的距离是奇数则必败，偶数必胜 
40         {
41             if(k>n)
42                 ans[k-n]=((j-k)&1)^1;
43             else
44                 ans[k]=((j-k)&1)^1;
45         }
46     }
47     for(int i=1;i<=n;i++)
48         if(ans[i])
49             printf("First
");
50         else
51             printf("Second
");
52     return 0;
53 }

博弈

E题，txdywjy的思路，就线段树区间维护两个懒标记，然后单点查询。具体的小细节有，首先叶子节点的每个数拆成质因子跟指数格式，然后在标记的传递上，乘的话就是增加最小质因子的个数，但除法的话减少最小质因子的个数，可能会造成最小质因子的改变，所以在标记的更新上，我们先处理除法的标记，再处理乘法的标记（还有wjytxdy）。

  1 //wjytxdy
  2 #include<cstdio>
  3 #include<vector>
  4 #define L(x) (x<<1)
  5 #define R(x) (x <<1|1)
  6 #define M(x) ((T[x].l+T[x].r)>>1)
  7 using namespace std;
  8 typedef long long ll;
  9 const int N=100118,mod=1000000007;
 10 struct Node{
 11     int val,num;
 12     Node(){}
 13     Node(int val,int num):val(val),num(num){} 
 14 };
 15 struct Tree{
 16     int l,r,lazy1,lazy2;//lazy1乘法标记，lazy2除法标记 
 17     vector<Node> pri;
 18 }T[N<<2];
 19 int a[N],pn,Pri[1000118];
 20 void init()//素数筛 
 21 {
 22     for(int i=2;i<=1000000;i++)
 23     {
 24         if(!Pri[i])
 25         {
 26             Pri[pn++]=i;
 27             for(int j=2;i*j<=1000000;j++)
 28                 Pri[i*j]=1;
 29         }
 30     }
 31 } 
 32 void built(int id,int l,int r)
 33 {
 34     T[id].l=l,T[id].r=r;
 35     T[id].lazy1=T[id].lazy2=0;
 36     if(l==r)
 37     {
 38         for(int i=0;i<pn&&Pri[i]*Pri[i]<=a[l];i++)//把叶子节点的数拆解质因子指数形式 
 39         {
 40             int num=0;
 41             if(a[l]%Pri[i])
 42                 continue;
 43             while(a[l]%Pri[i]==0)
 44             {
 45                 num++;
 46                 a[l]/=Pri[i];
 47             }
 48             T[id].pri.push_back(Node(Pri[i],num));
 49         }
 50         if(a[l]!=1) 
 51             T[id].pri.push_back(Node(a[l],1));
 52         return ;
 53     }
 54     built(L(id),l,M(id));
 55     built(R(id),M(id)+1,r);
 56 }
 57 void modify(int id,int op,int num)//修改节点消息 
 58 {
 59     if(op==1)
 60         T[id].lazy1+=num;//乘法标记直接加上 
 61     if(op==2)//除法标记先抵消掉之前的乘法标记再加上 
 62     {
 63         if(T[id].lazy1>=num)
 64             T[id].lazy1-=num;
 65         else
 66         {
 67             num-=T[id].lazy1;
 68             T[id].lazy1=0;
 69             T[id].lazy2+=num;
 70         }
 71     }
 72 }
 73 void down(int id)//懒标记下传 
 74 {
 75     modify(L(id),2,T[id].lazy2);
 76     modify(L(id),1,T[id].lazy1);
 77     modify(R(id),2,T[id].lazy2);
 78     modify(R(id),1,T[id].lazy1);
 79     T[id].lazy1=T[id].lazy2=0;
 80 }
 81 void updata(int id,int l,int r,int op)//区间更新懒标记 
 82 {
 83     if(T[id].l>=l&&r>=T[id].r)
 84     {
 85         modify(id,op,1);
 86         return ;
 87     }
 88     if(T[id].lazy1||T[id].lazy2)
 89         down(id);
 90     if(l<=M(id))
 91         updata(L(id),l,r,op);
 92     if(r>M(id))
 93         updata(R(id),l,r,op);
 94 }
 95 ll pow(ll a,int p)
 96 {
 97     ll ans=1;
 98     while(p)
 99     {
100         if(p&1)
101             ans=(ans*a)%mod;
102         p>>=1;
103         a=(a*a)%mod;
104     }
105     return ans;
106 }
107 ll query(int id,int pos)//单点查询 
108 {
109     if(T[id].l==pos&&T[id].r==pos)
110     {
111         ll ans=1;
112         for(int i=0;i<T[id].pri.size();i++)//先将除法标记处理完 
113         {
114             if(!T[id].pri[i].num)
115                 continue;
116             if(T[id].pri[i].num>=T[id].lazy2)
117             {
118                 T[id].pri[i].num-=T[id].lazy2;
119                 break;
120             }
121             else
122             {
123                 T[id].lazy2-=T[id].pri[i].num;
124                 T[id].pri[i].num=0;
125             }
126         }
127         for(int i=0;i<T[id].pri.size();i++)//再处理乘法标记并计算答案 
128         {
129             if(!T[id].pri[i].num)
130                 continue;
131             T[id].pri[i].num+=T[id].lazy1;//最小质因子加上乘法标记 
132             T[id].lazy1=0;//清空 
133             ans=(ans*pow(1ll*T[id].pri[i].val,T[id].pri[i].num))%mod;
134         }
135         T[id].lazy1=T[id].lazy2=0;
136         return ans%mod;
137     }
138     if(T[id].lazy1||T[id].lazy2)
139         down(id);
140     if(pos<=M(id))
141         return query(L(id),pos);
142     else 
143         return query(R(id),pos);
144 }
145 int main()
146 {
147     int n,m,l,r,op;
148     scanf("%d%d",&n,&m);
149     for(int i=1;i<=n;i++)
150         scanf("%d",&a[i]);
151     init();
152     built(1,1,n);
153     while(m--)
154     {
155         scanf("%d%d",&op,&l);
156         if(op==3)
157             printf("%lld
",query(1,l));
158         else
159         {
160             scanf("%d",&r);
161             updata(1,l,r,op);
162         }
163     }
164     return 0;
165 }

线段树

C题，补题补的，长见识了，第一次见到map里套vector的，不过string也可以。这题思路很简单自己想复杂了，如果只有一个图的话，并查集或者图的dfs涂色都可以，而多个图的话，如果两个点在每个图都连通，那么它们相应的集合编号序列是一样的，所以map记录每个集合编号序列有多少个就行。

 1 #include<iostream>
 2 #include<vector>
 3 #include<map>
 4 #include<cstdio>
 5 #include<algorithm>
 6 using namespace std;
 7 const int N=100118;
 8 int n,k,fa[N][18];
 9 vector<int> vv[N]; 
10 map< vector<int>,int > mmp;
11 void init()
12 {
13     mmp.clear();
14     for(int i=0;i<=n;i++)
15     {
16         vv[i].clear();
17         for(int j=0;j<=k;j++)
18             fa[i][j]=i;
19     }
20 }
21 int gui(int x,int y){
22     return fa[x][y]==x ? x : fa[x][y]=gui(fa[x][y],y);
23 }
24 void bing(int u,int v,int y)
25 {
26     int gu=gui(u,y),gv=gui(v,y);
27     if(gu!=gv)
28         fa[gv][y]=fa[gu][y];
29 }
30 int main()
31 {
32     int a,u,v;
33     while(~scanf("%d%d",&n,&k))
34     {
35         init();
36         for(int i=0;i<k;i++)
37         {
38             scanf("%d",&a);
39             while(a--)
40             {
41                 scanf("%d%d",&u,&v);
42                 bing(u,v,i);//并查集把i这张图的u和v连一起 
43             }
44         }
45         for(int i=1;i<=n;i++)
46         {
47             for(int j=0;j<k;j++)
48                 vv[i].push_back(gui(i,j));//记录集合编号序列 
49             mmp[vv[i]]++;
50         }
51         for(int i=1;i<=n;i++)
52             printf("%d
",mmp[vv[i]]);
53     }
54     return 0;
55 }

多图涂色

剩下神仙题不会了