六道普及组题，没啥好说的
场上预计得分：100+100+100+100+100+100=600（省一分数线490）
（AK是不可能AK的，这辈子不可能AK的）
题解：
D1T1 生活大爆炸版石头剪刀布
水题送温暖~
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 #include<queue>
7 #define inf 2147483647
8 #define eps 1e-9
9 using namespace std;
10 typedef long long ll;
11 const int ch[5][5]={{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};
12 int n,n1,n2,ans1,ans2,a[201],b[201];
13 int main(){
14 scanf("%d%d%d",&n,&n1,&n2);
15 for(int i=0;i<n1;i++){
16 scanf("%d",&a[i]);
17 }
18 for(int i=0;i<n2;i++){
19 scanf("%d",&b[i]);
20 }
21 for(int i=1;i<=n;i++){
22 ans1+=ch[a[(i-1)%n1]][b[(i-1)%n2]];
23 ans2+=ch[b[(i-1)%n2]][a[(i-1)%n1]];
24 }
25 printf("%d %d",ans1,ans2);
26 return 0;
27 }
D1T2 联合权值
和一个同点相连的两个点一定会产生联合权值；
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 #include<queue>
7 #define inf 2147483647
8 #define eps 1e-9
9 #define mod 10007
10 using namespace std;
11 typedef long long ll;
12 struct edge{
13 int v,next;
14 }a[500001];
15 int n,u,v,tot=0,ans=-inf,anss=0,top,s[200001],num[200001],head[200001];
16 void add(int u,int v){
17 a[++tot].v=v;
18 a[tot].next=head[u];
19 head[u]=tot;
20 }
21 void work(int u){
22 int sum=0,mx=-inf,mmx=-inf;
23 top=0;
24 for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
25 int v=a[tmp].v;
26 s[++top]=v;
27 sum+=num[v];
28 if(num[v]>mx){
29 mmx=mx;
30 mx=num[v];
31 }else mmx=max(mmx,num[v]);
32 }
33 if(top<2)return;
34 ans=max(ans,mx*mmx);
35 for(int i=1;i<=top;i++){
36 anss=(anss+(ll)num[s[i]]*(sum-num[s[i]]))%mod;
37 }
38 }
39 int main(){
40 memset(head,-1,sizeof(head));
41 scanf("%d",&n);
42 for(int i=1;i<n;i++){
43 scanf("%d%d",&u,&v);
44 add(u,v);
45 add(v,u);
46 }
47 for(int i=1;i<=n;i++)scanf("%d",&num[i]);
48 for(int i=1;i<=n;i++){
49 work(i);
50 }
51 printf("%d %d",ans,anss);
52 return 0;
53 }
D1T3 飞扬的小鸟
唯一可能有点思维难度的题？70分显然，正解就向上向下分两种背包（01和完全）转移即可；
（1A爽爽）
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 #include<queue>
7 #define inf 0x7f7f7f7f
8 #define eps 1e-9
9 using namespace std;
10 typedef long long ll;
11 int n,m,k,p,L,H,tmp,ans=inf,x[10001],y[10001],l[10001],h[10001],f[10001][1001];
12 bool isp[10001];
13 int main(){
14 memset(f,0x7f,sizeof(f));
15 memset(isp,0,sizeof(isp));
16 scanf("%d%d%d",&n,&m,&k);
17 for(int i=1;i<=n;i++){
18 scanf("%d%d",&x[i],&y[i]);
19 l[i]=0;
20 h[i]=m+1;
21 }
22 for(int i=1;i<=k;i++){
23 scanf("%d%d%d",&p,&L,&H);
24 isp[p]=true;
25 l[p]=L;
26 h[p]=H;
27 }
28 for(int i=1;i<=m;i++)f[0][i]=0;
29 for(int i=1;i<=n;i++){
30 for(int j=x[i]+1;j<=m;j++){
31 f[i][j]=min(f[i][j],f[i-1][j-x[i]]+1);
32 f[i][j]=min(f[i][j],f[i][j-x[i]]+1);
33 }
34 for(int j=m-x[i];j<=m;j++){
35 f[i][m]=min(f[i][m],min(f[i][j]+1,f[i-1][j]+1));
36 }
37 for(int j=l[i]+1;j<h[i];j++){
38 if(j+y[i]<=m){
39 f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
40 }
41 }
42 for(int j=0;j<=l[i];j++)f[i][j]=inf;
43 for(int j=h[i];j<=m;j++)f[i][j]=inf;
44 }
45 for(int i=1;i<=m;i++){
46 ans=min(ans,f[n][i]);
47 }
48 if(ans==inf){
49 ans=0;
50 for(int i=1;i<=n;i++){
51 tmp=inf;
52 for(int j=1;j<=m;j++)tmp=min(tmp,f[i][j]);
53 if(tmp==inf)break;
54 if(isp[i])ans++;
55 }
56 printf("0
%d",ans);
57 }else printf("1
%d",ans);
58 return 0;
59 }
D2T1 无线网络发射器选址
水题送温暖~
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 #include<queue>
7 #define inf 2147483647
8 #define eps 1e-9
9 using namespace std;
10 typedef long long ll;
11 int n,d,x,y,k,ans=0,tmp,anss=0,mp[201][201];
12 int main(){
13 scanf("%d%d",&d,&n);
14 for(int i=1;i<=n;i++){
15 scanf("%d%d%d",&x,&y,&k);
16 mp[x][y]=k;
17 }
18 for(int i=0;i<=128;i++){
19 for(int j=0;j<=128;j++){
20 tmp=0;
21 for(int x=max(i-d,0);x<=min(i+d,128);x++){
22 for(int y=max(j-d,0);y<=min(j+d,128);y++){
23 tmp+=mp[x][y];
24 }
25 }
26 if(tmp>ans){
27 ans=tmp;
28 anss=1;
29 }else if(tmp==ans)anss++;
30 }
31 }
32 printf("%d %d",anss,ans);
33 return 0;
34 }
D2T2 寻找道路
什么时候裸的最短路可以上D2T2了？？显然建反向边把不能到达的点判掉，然后裸的最短路；
（并没有卡SPFA好评）
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 #include<queue>
7 #define inf 2147483647
8 #define eps 1e-9
9 using namespace std;
10 typedef long long ll;
11 struct edge{
12 int v,next;
13 }a[200001],_a[200001];
14 int n,m,u,v,vs,vt,tot=0,_tot=0,head[100001],_head[100001],sp[100001];
15 bool isin[100001],used[100001],vis[100001];
16 void add(int u,int v){
17 a[++tot].v=v;
18 a[tot].next=head[u];
19 head[u]=tot;
20 }
21 void _add(int u,int v){
22 _a[++_tot].v=v;
23 _a[_tot].next=_head[u];
24 _head[u]=_tot;
25 }
26 void bfs(int s){
27 queue<int>q;
28 q.push(s);
29 used[s]=true;
30 while(!q.empty()){
31 int u=q.front();
32 q.pop();
33 for(int tmp=_head[u];tmp!=-1;tmp=_a[tmp].next){
34 int v=_a[tmp].v;
35 if(!used[v]){
36 used[v]=true;
37 q.push(v);
38 }
39 }
40 }
41 }
42 void spfa(int s){
43 memset(isin,0,sizeof(isin));
44 memset(sp,0x3f,sizeof(sp));
45 queue<int>q;
46 q.push(s);
47 isin[s]=true;
48 sp[s]=0;
49 while(!q.empty()){
50 int u=q.front();
51 q.pop();
52 isin[u]=false;
53 for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
54 int v=a[tmp].v;
55 if(vis[v]&&sp[v]>sp[u]+1){
56 sp[v]=sp[u]+1;
57 if(!isin[v]){
58 isin[v]=true;
59 q.push(v);
60 }
61 }
62 }
63 }
64 }
65 int main(){
66 memset(used,0,sizeof(used));
67 memset(head,-1,sizeof(head));
68 memset(_head,-1,sizeof(_head));
69 scanf("%d%d",&n,&m);
70 for(int i=1;i<=m;i++){
71 scanf("%d%d",&u,&v);
72 if(u==v)continue;
73 add(u,v);
74 _add(v,u);
75 }
76 scanf("%d%d",&vs,&vt);
77 bfs(vt);
78 if(!used[vs])return printf("-1"),0;
79 for(int i=1;i<=n;i++){
80 vis[i]=true;
81 for(int tmp=head[i];tmp!=-1;tmp=a[tmp].next){
82 int v=a[tmp].v;
83 vis[i]&=used[v];
84 }
85 }
86 spfa(vs);
87 printf("%d",sp[vt]);
88 return 0;
89 }
D2T3 解方程
无力吐槽了……一道跟D1T1一样水的题放在D2T3是想考我们读题能力吗……还是考字符串转化成数字的处理？？
枚举解，把所有系数膜一个大质数即可；
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 #include<queue>
7 #define inf 2147483647
8 #define eps 1e-9
9 #define mod 998244353
10 using namespace std;
11 typedef long long ll;
12 int rd(){
13 int x=0,f=1;
14 char ch;
15 do{
16 ch=getchar();
17 if(ch=='-')f=-1;
18 }while(!isdigit(ch));
19 do{
20 x=((ll)x*10+ch-'0')%mod;
21 ch=getchar();
22 }while(isdigit(ch));
23 if(f==-1)x=mod-x;
24 return x;
25 }
26 int n,m,ans=0,anss[100001],num[101];
27 void work(int x){
28 ll nw=1,ret=0;
29 for(int i=0;i<=n;i++){
30 ret=(ret+(ll)nw*num[i]%mod+mod)%mod;
31 nw=(nw*x)%mod;
32 }
33 if(ret==0)anss[++ans]=x;
34 }
35 int main(){
36 scanf("%d%d",&n,&m);
37 for(int i=0;i<=n;i++){
38 num[i]=rd();
39 }
40 for(int i=1;i<=m;i++){
41 work(i);
42 }
43 printf("%d
",ans);
44 for(int i=1;i<=ans;i++){
45 printf("%d
",anss[i]);
46 }
47 return 0;
48 }
总结：
早就听说很水，没想到这么水……晚上无聊写写一个半小时不到写完了……“当你走进提高组考场考了六道普及组题目是怎样一种体验”