西南民族大学第十届校赛-解题记录

重现地址：牛客重现赛

A.dreamstart的催促

这是快速幂的模板题，注意$(a + b)\% c = ((a\% c) + (b\% c))\% c$

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 const int maxn = 1e5+5;
 5 const long long MOD = 10000019;
 6 long long num[maxn];
 7 int N;
 8 void Init()
 9 {
10     for(int i=0;i<N;i++)
11         scanf("%lld",&num[i]);
12 }
13 long long getnum(long long a,long long b)
14 {
15     long long res = 1;
16     while(b)
17     {
18         if(b&1) res = res*a%MOD;
19         a = a*a%MOD;
20         b >>= 1;
21     }
22     return res;
23 }
24 void Solve()
25 {
26     long long ans = 0;
27     for(int i=0;i<N;i++)
28         ans += getnum(num[i],i+1);
29     ans = ans%MOD;
30     printf("%lld
",ans);
31 }
32 int main()
33 {
34     while(scanf("%d",&N)!=EOF)
35     {
36         Init();
37         Solve();
38     }  
39     return 0;
40 }
View Code

 B.TRDD got lost again

一看就是BFS的搜索题，唯一特殊的移动的步幅为2。同时注意有两个坑：1.输入包含空格，用scanf会超时；2.题目卡空间，标记数组vis用bool不要用int

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <queue>
 6 using namespace std;
 7 const int maxn = 6005;
 8 char Map[maxn][maxn],c;
 9 int N,M;
10 bool vis[maxn][maxn];
11 int Sx,Sy,Tx,Ty;
12 int dx[4] = {0,2,0,-2};
13 int dy[4] = {2,0,-2,0};
14 struct Node
15 {
16     int x,y,t;
17     Node(){}
18     Node(int xx,int yy,int tt)
19     {
20         x = xx;
21         y = yy;
22         t = tt;
23     }
24 };
25 void Init()
26 {
27     N = N*2+1;
28     M = M*2+1;
29     for(int i=0;i<N;i++)
30     {
31         getchar();
32         for(int j=0;j<M;j++)
33         {
34             Map[i][j]=getchar();
35             if(Map[i][j]=='S')
36             {
37                 Sx=i;
38                 Sy=j;
39             }
40             if(Map[i][j]=='T')
41             {
42                 Tx=i;
43                 Ty=j;
44             }
45         }
46     }
47     memset(vis,false,sizeof(vis));
48 }
49 void Solve()
50 {
51     int ans = -1;
52     queue<Node> Q;
53     Q.push(Node(Sx,Sy,1));
54     vis[Sx][Sy] = 1;
55     while(!Q.empty())
56     {
57         Node temp = Q.front();
58         Q.pop();
59         if(Map[temp.x][temp.y] == 'T')
60         {
61             ans = temp.t;
62             break;
63         }
64         for(int i=0;i<4;i++)
65         {
66             int nx = temp.x+dx[i];
67             int ny = temp.y+dy[i];
68             int tempx = temp.x+dx[i]/2;
69             int tempy = temp.y+dy[i]/2;
70             if(nx>=1&&nx<N&&ny>=1&&ny<M)
71             {
72                 if((Map[tempx][tempy]==' ')&&(Map[nx][ny]==' '||Map[nx][ny]=='T'))
73                     if(!vis[nx][ny])
74                     {
75                         Q.push(Node(nx,ny,temp.t+1));
76                         vis[nx][ny] = true;
77                     }
78             }
79         }  
80     }
81     if(ans>0)
82         printf("%d
",ans);
83     else
84         printf("TRDD Got lost...TAT
");   
85 }
86 int main()
87 {
88     while(scanf("%d%d",&N,&M)!=EOF)
89     {
90         Init();
91         Solve();
92     }
93     return 0;
94 }
View Code

C.Company

所有的村庄是一个树的结构，某个节点的答案来自于两个部分：1.该节点的所有子节点的答案和；2.该节点自身是否劳动力不足，不足就为1，否则为0

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <vector>
 4 # include <cstring>
 5 using namespace std;
 6 const int maxn = 2e5+10;
 7 int num[maxn],vis[maxn],ans[maxn];
 8 vector<int> G[maxn];
 9 int n,k;
10 void Init()
11 {
12     int u,v;
13     for(int i=1;i<=n;i++)
14         scanf("%d",&num[i]);
15     for(int i=0;i<maxn;i++)
16         G[i].clear();
17     for(int i=0;i<n-1;i++)
18     {
19         scanf("%d%d",&u,&v);
20         G[u].push_back(v);
21         G[v].push_back(u);
22     }
23     memset(vis,0,sizeof(vis));
24     memset(ans,0,sizeof(ans));
25 }
26 void dfs(int x)
27 {
28     if(num[x]<=k)
29         ans[x]++;
30     for(int i=0;i<G[x].size();i++)
31     {
32         if(!vis[G[x][i]])
33         {
34             vis[G[x][i]] = 1;
35             dfs(G[x][i]);
36             ans[x] += ans[G[x][i]];    
37         }        
38     }
39 }
40 void Solve()
41 {
42     vis[1] = 1;
43     dfs(1);
44     for(int i=1;i<=n;i++)
45     {
46         if(i<n)
47             printf("%d ",ans[i]);
48         else
49             printf("%d
",ans[i]);
50     }
51 }
52 int main()
53 {
54     while(scanf("%d%d",&n,&k)!=EOF)
55     {
56         Init();
57         Solve();
58     }    
59     return 0;
60 }
View Code

D.A-B-C

一个简单模拟题

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 const int maxn = 5005;
 5 int N,num[maxn];
 6 void Init()
 7 {
 8     for(int i=1;i<=N;i++)
 9         scanf("%d",&num[i]);
10 }
11 void Solve()
12 {
13     int f = 0;
14     for(int i=1;i<=N;i++)
15     {
16         int l = num[i];
17         int ll = num[l];
18         if(i==num[ll])
19         {
20             f = 1;
21             break;
22         }    
23     }
24     if(f) printf("YES
");
25     else printf("NO
");
26 }
27 int main()
28 {
29     while(scanf("%d",&N)!=EOF)
30     {
31         Init();
32         Solve();
33     }
34     return 0;
35 }
View Code

E.PPY的字符串

模拟题，我用结构体存储字符串的信息,112333-》(2,1)(1,2)(3,3)

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxn = 1e5;
 6 struct Node
 7 {
 8     char c;
 9     int n;
10     Node(){}
11     Node(char cc,int nn)
12     {
13         c = cc;
14         n = nn;
15     }
16 };
17 Node ss[maxn];
18 char s[maxn];
19 int N;
20 void change()
21 {
22     int k = 0;
23     char tempnum = s[0];
24     int tempcnt = 1;
25     int L = strlen(s);
26     for(int i=1;i<L;i++)
27     {
28         if(s[i]==tempnum)
29             tempcnt++;
30         else
31         {
32             ss[k++] = Node(tempnum,tempcnt);
33             tempnum = s[i];
34             tempcnt = 1;
35         } 
36     }
37     ss[k++] = Node(tempnum,tempcnt);
38     int f = 0;
39     for(int i=0;i<k;i++)
40     {
41         s[f++] = char(ss[i].n+'0');
42         s[f++] = ss[i].c;
43     }
44     s[f] = '';
45 }
46 void Solve()
47 {
48     for(int i=0;i<N-1;i++)
49         change();
50     printf("%d %s
",strlen(s),s);
51 }
52 int main()
53 {
54     while(scanf("%s%d",s,&N)!=EOF)
55     {
56         Solve();
57     }
58     return 0;
59 }
View Code

F.集训队的脱单大法

数据很水，暴力求解

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cmath>
 4 using namespace std;
 5 const int maxn = 1e5+5;
 6 int num[maxn];
 7 int n;
 8 void Init()
 9 {
10     for(int i=0;i<n;i++)
11         scanf("%d",&num[i]);
12 }
13 int getmax(int l,int r)
14 {
15     int res = -1;
16     for(int i=l;i<=r;i++)
17         res = max(res,num[i]);
18     return res;
19 }
20 void Solve()
21 {
22     int res = -1;
23     for(int i=0;i<n-1;i++)
24     {
25         int Lmax = getmax(0,i);
26         int Rmax = getmax(i+1,n-1);
27         res = max(res,abs(Lmax-Rmax));
28     }
29     printf("%d
",res);
30 }
31 int main()
32 {
33     while(scanf("%d",&n)!=EOF)
34     {
35         Init();
36         Solve();
37     }    
38     return 0;
39 }
View Code

G.不想再WA了

数据很水，直接dfs

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 const int maxn = 105;
 5 int cnt,N,s[maxn];
 6 void Init()
 7 {
 8     scanf("%d",&N);
 9     cnt = 0;    
10 }
11 bool judge()
12 {
13     for(int i=0;i+1<N;i++)
14         if(s[i]==3&&s[i+1]==1)
15             return false;
16     return true;
17 }
18 void dfs(int len)
19 {
20     if(len==N)
21     {
22         if(judge())    cnt++;
23         return;        
24     }
25     else
26     {
27         for(int i=1;i<=3;i++)
28         {
29             s[len] = i;
30             dfs(len+1);
31         }    
32     }
33 }
34 void Solve()
35 {
36     dfs(0);
37     printf("%d
",cnt);
38 }
39 int main()
40 {
41     int T;
42     scanf("%d",&T);
43     while(T--)
44     {
45         Init();
46         Solve();            
47     }
48     return 0;
49 }
View Code

H.Ricky’s RealDan’s Ricky

博弈题，找规律，只有娃娃机个数为 1 个， 并且里面的娃娃只有偶数个， 第一个人才能赢 

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 const int maxn = 1e5+5;
 5 int num[maxn];
 6 int main()
 7 {
 8     int T,n;
 9     scanf("%d",&T);
10     while(T--)
11     {
12         scanf("%d",&n);
13         for(int i=0;i<n;i++)
14             scanf("%d",&num[i]);
15         if(n==1&&num[0]%2==0)
16             printf("Ricky is Winner
");
17         else
18             printf("RealDan is Winner
");
19     }    
20     return 0;
21 }
View Code

I.小A的期末作业

纯模拟，注意最后输出50个就要加一个空行

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cmath>
 4 using namespace std;
 5 int main()
 6 {
 7     int N;
 8     while(scanf("%d",&N)!=EOF)
 9     {
10         for(int i=0;i<2*N-1;i++)
11         {
12             int spL = N-1-abs(N-1-i);
13             for(int j=0;j<spL;j++)
14                 printf(" ");
15             for(int j=0;j<N;j++)
16                 printf("*");
17             printf("
");
18         }
19     }
20     return 0;
21 }
View Code

J.怪盗基德 & 月之瞳宝石

模拟题，在星体和能源体的分布上，遍历每一个星体，找到与这个星体最近能源体的距离，在所有的最近距离中取最大的就是答案

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <algorithm> 
 4 # include <cmath>
 5 using namespace std;
 6 const int maxn = 1e5+10;
 7 long long s[maxn],p[maxn]; 
 8 int n,m;
 9 void Init()
10 {
11     for(int i=0;i<n;i++)
12         scanf("%lld",&s[i]);
13     for(int i=0;i<m;i++)
14         scanf("%lld",&p[i]);    
15 }
16 void Solve()
17 {
18     sort(s,s+n);
19     sort(p,p+m);
20     long long ans,temp;
21     int j = 0;
22     ans = -1;
23     for(int i=0;i<n;i++)
24     {
25         while(p[j]<s[i]&&j<m-1) j++;
26         //printf("%d %d %d %d
",j,p[j-1],s[i],p[j]);
27         if(j==0) temp = abs(p[j] - s[i]);
28         else temp = min(abs(p[j] - s[i]),abs(s[i] - p[j-1]));
29         //printf("%lld
",temp);
30         ans = max(ans,temp);
31     }    
32     printf("%lld
",ans);
33 }
34 int main()
35 {
36     while(scanf("%d%d",&n,&m)!=EOF)
37     {
38         Init();
39         Solve();
40     } 
41     return 0;
42 }
View Code

K.正方体

模拟题

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 int Map[4][5];
 5 void Init()
 6 {
 7     for(int i=0;i<3;i++)
 8         for(int j=0;j<4;j++)
 9             scanf("%d",&Map[i][j]);
10 }
11 void Solve()
12 {
13     int a,b;
14     for(int i=0;i<4;i++)
15     {
16         if(Map[0][i]!=0) a = Map[0][i];
17         if(Map[2][i]!=0) b = Map[2][i];
18     }
19     if(a!=b||Map[1][0]!=Map[1][2]||Map[1][1]!=Map[1][3])
20         printf("No!
");
21     else
22         printf("Yes!
");
23 }
24 int main()
25 {
26     int T;
27     scanf("%d",&T);
28     for(int i=0;i<T;i++)
29     {
30         Init();
31         Solve();
32         if((i+1)%50==0)
33             printf("
");
34     }
35     return 0;
36 }
View Code

L.简单的分数

运用gcd公式通分，注意处理负号的问题

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cmath>
 4 using namespace std;
 5 int op,a,b,c,d;
 6 void Init()
 7 {
 8     scanf("%d%d%d%d%d",&op,&a,&b,&c,&d);    
 9 }
10 int gcd(int x,int y)
11 {
12     return y?gcd(y,x%y):x;
13 }
14 void Solve()
15 {
16     int bd = b*d;
17     int adbc = op==1?a*d+b*c:a*d-b*c;
18     int temp = gcd(abs(bd),abs(adbc));
19     printf("%d/%d
",adbc/temp,bd/temp);
20 }
21 int main()
22 {
23     int T;
24     scanf("%d",&T);
25     while(T--)
26     {
27         Init();
28         Solve();
29     }    
30     return 0;
31 }
View Code

M.HJ浇花

运用差分标记能够很快很巧妙的处理区间处理的问题吗，推荐一个讲的清楚的博客

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxn = 1e6+10;
 6 int num[maxn],sum[maxn],cnt[maxn];
 7 int n;
 8 void Init()
 9 {
10     memset(cnt,0,sizeof(cnt));
11     memset(sum,0,sizeof(sum));
12     memset(num,0,sizeof(num));
13 }
14 void Solve()
15 {
16     int l,r;
17     for(int i=0;i<n;i++)
18     {
19         scanf("%d%d",&l,&r);
20         sum[l]++;
21         sum[r+1]--;
22     }
23     int res = 0;
24     num[0] = sum[0];
25     cnt[num[0]]++;
26     for(int i=1;i<maxn;i++)
27     {
28         num[i] = num[i-1] + sum[i];
29         cnt[num[i]]++;
30     }
31     for(int i=1;i<n;i++)
32         printf("%d ",cnt[i]);
33     printf("%d
",cnt[n]);
34 }
35 int main()
36 {
37     while(scanf("%d",&n)!=EOF)
38     {
39         Init();
40         Solve();
41     }
42     return 0;
43 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cnXuYang/p/10245024.html