格式坏掉了,可以去
西南民族大学第十届校赛(同步赛)
打了11道,果然AK是这辈子也不可能的么QAQ
A dreamstart的催促
快速幂。。。
1 | 1 #include<iostream> |
A
B TRDD got lost again
很麻烦的一道题,我的做法是先把图转成n*m的,然后用二进制记录是否可以通过,再dfs。一开始cin.getline()超时,后来用的gets()。
1 | 1 #include<iostream> |
B
C Company
递归,返回下面的值并记录,一开始以为先求深度,后来发现不用。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 200020*2
7 int n,k;
8 int pe[MAXN];
9 struct Edge{
10 int u,v,next;
11 }e[MAXN];
12 int g[MAXN];
13 int dep[MAXN],f[MAXN],kk[MAXN];
14 int dfs(int cur,int d){
15 dep[cur]=d;
16 f[cur]=1;
17 int ans=0;
18 for(int i=g[cur];i>0;i=e[i].next){
19 int v=e[i].v;
20 if(!f[v]){
21 ans+=dfs(v,d+1);
22 }
23 }
24 if(pe[cur]<=k) return kk[cur]=ans+1;
25 return kk[cur]=ans;
26 }
27 int main(){
28 scanf("%d%d",&n,&k);
29 for(int i=1;i<=n;i++){
30 scanf("%d",&pe[i]);
31 }
32 int xx,yy;
33 for(int i=1;i<=n-1;i++){
34 scanf("%d%d",&xx,&yy);
35 e[i]=(Edge){xx,yy,g[xx]};g[xx]=i;
36 e[i+n-1]=(Edge){yy,xx,g[yy]};g[yy]=i+n-1;
37 }
38 dfs(1,1);
39 for(int i=1;i<=n;i++){
40 printf("%d ",kk[i]);
41 }
42
43 return 0;
44 }
D >A->B->C-
从任意一个点能搜3个回来就可以。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int n,a[5020],f[5020],k=0;
8 void dfs(int rig,int x,int d){
9 if(d==4){
10 if(rig==x){
11 k=1;
12 }
13 return;
14 }
15 dfs(rig,a[x],d+1);
16 }
17 int main(){
18 cin>>n;
19 for(int i=1;i<=n;i++){
20 scanf("%d",&a[i]);
21 }
22 for(int i=1;i<=n;i++){
23 dfs(i,i,1);
24 if(k==1) break;
25 }
26 if(k==1) printf("YES\n");
27 else{
28 printf("NO\n");
29 }
30 return 0;
31 }
D
E PPY的字符串
模拟,数组要开大一点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 #define MOD 10000019
6 #define ll long long
7 #define MAXN 1000020
8 int a[500000],b[500000],l=0;
9 int n,aa;
10 void fun(){
11 int nl=0,cur=a[1],cnt=0;
12 for(int i=1;i<=l;i++){
13 if(a[i]==cur){
14 cnt++;
15 }
16 if((a[i+1]!=cur&&i<l)||i==l){
17 b[++nl]=cnt;
18 b[++nl]=cur;
19 cnt=0;
20 cur=a[i+1];
21 }
22 }
23
24 l=nl;
25 }
26 int main(){
27 cin>>aa>>n;
28
29 for(int i=1;aa;i++){
30 a[i]=aa%10;
31 aa/=10 ;
32 l++;
33 }
34 for(int i=1;i<=l/2;i++){
35 swap(a[i],a[l-i+1]);
36 }
37 /*for(int i=1;i<=l;i++){
38 printf("%d",a[i]);
39 }*/
40 for(int i=1;i<=n-1;i++){
41 memset(b,0,sizeof(b));
42 fun();
43 for(int j=1;j<=l;j++){
44 a[j]=b[j];
45 }
46 }
47 cout<<l<<' ';
48 for(int i=1;i<=l;i++){
49 printf("%d",a[i]);
50 }
51 cout<<endl;
52 return 0;
53 }```
E
F [集训队脱单大法:这是一道只能由学姐我自己出数据的水题](https://ac.nowcoder.com/acm/contest/322/F)
左边找最大值,右边找最大值。
即使分成两半也让单身狗羡慕至极呢
![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int n,ans;
8 int a[MAXN];
9 int lm[MAXN],rm[MAXN];
10 int abss(int a){
11 return a>0?a:-a;
12 }
13 int main(){
14 cin>>n;
15 for(int i=1;i<=n;i++){
16 scanf("%d",&a[i]);
17 }
18 for(int i=1;i<=n-1;i++){
19 lm[i]=max(lm[i-1],a[i]);
20 }
21 for(int i=n-1;i>=1;i--){
22 rm[i]=max(a[i+1],rm[i+1]);
23 }
24 for(int i=1;i<=n-1;i++){
25 ans=max(ans,abss(lm[i]-rm[i]));
26 }
27 cout<<ans<<endl;
28 return 0;
29 }```
F
G 不想再WA了
DFS赋值写一遍,然后愉快地打表咯。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int ANS[20]={0,3,8,21,55,144,377,987,2584,6765,17711};
8 int T,n;
9 int main(){
10 cin>>T;
11 while(T--){
12 cin>>n;
13 printf("%d\n",ANS[n]);
14 }
15 return 0;
16 }```
G
H [Ricky's RealDan's Ricky](https://ac.nowcoder.com/acm/contest/322/H)
更新,RealDan拥有把偶数变成奇数的神奇能力,所以只要Ricky一次不能赢,就输了。
当只有一堆且为偶数是为Ricky胜
![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int T,n;
5 int a[100020];
6 int main(){
7 cin>>T;
8 while(T--){
9 scanf("%d",&n);
10 for(int i=1;i<=n;i++){
11 scanf("%d",&a[i]);
12 }
13 if(n==1&&a[1]%2==0){
14 cout<<"Ricky is Winner"<<endl;
15 }
16 else{
17 cout<<"RealDan is Winner"<<endl;
18 }
19 }
20 return 0;
21 }```
H
I 小A的期末作业
C++语言入门题。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int n;
8 int main(){
9 cin>>n;
10 for(int i=1;i<=n-1;i++){
11 for(int j=1;j<=i-1;j++){
12 printf(" ");
13 }
14 for(int j=1;j<=n;j++){
15 printf("*");
16 }
17 cout<<endl;
18 }
19 for(int i=1;i<=n-1;i++){
20 printf(" ");
21 }
22 for(int i=1;i<=n;i++){
23 printf("*");
24 }
25 cout<<endl;
26 for(int i=n-1;i>=1;i--){
27 for(int j=1;j<=i-1;j++){
28 printf(" ");
29 }
30 for(int j=1;j<=n;j++){
31 printf("*");
32 }
33 cout<<endl;
34 }
35 return 0;
36 }```
I
J [怪盗基德 & 月之瞳宝石](https://ac.nowcoder.com/acm/contest/322/J)
二分,这是伟大玄学的胜利。
![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<string>
6 #include<algorithm>
7 using namespace std;
8 #define MOD 10000019
9 #define ll long long
10 #define MAXN 1000020
11 int n,m;
12 int a[100020],b[100020];
13 bool fun(ll s){
14 int cur=1;
15 ll xl=b[1]-s,xr=b[1]+s;
16 for(int i=1;i<=n;i++){
17 if(a[i]<xl){
18 return false;
19 }
20 if(a[i]>xr){
21 while(a[i]>xr||a[i]<xl){
22 cur++;
23 xl=b[cur]-s;
24 xr=b[cur]+s;
25 if(cur>m){
26 return false;
27 }
28 }
29 }
30 }
31 return true;
32 }
33 int main(){
34 cin>>n>>m;
35 for(int i=1;i<=n;i++){
36 scanf("%d",&a[i]);
37 }
38 for(int j=1;j<=m;j++){
39 scanf("%d",&b[j]);
40 }
41 sort(a+1,a+1+n);
42 sort(b+1,b+1+m);
43 ll l=0,r=4e9+1;
44 while(l<r){
45 ll mid=(l+r)/2;
46 if(fun(mid)){
47 r=mid;
48 }
49 else{
50 l=mid+1;
51 }
52 }
53 printf("%lld\n",l);
54 // printf("%d",fun(4));
55 return 0;
56 }```
J
K 正方体
第一遍不知道为什么WA,修改了一下1,3行赋值就对了,图形限定这么严格也是入门题了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 #define MOD 10000019
6 #define ll long long
7 #define MAXN 1000020
8 ll a[10][10];
9 int T;
10 int main(){
11 cin>>T;
12 for(int i=1;i<=T;i++){
13 memset(a,0,sizeof(a));
14 ll x=0,y=0;
15 for(int j=1;j<=3;j++){
16 for(int k=1;k<=4;k++){
17 scanf("%lld",&a[j][k]);
18 if(j==1&&a[j][k]){
19 x=a[j][k];
20 }
21 if(j==3&&a[j][k]){
22 y=a[j][k];
23 }
24 }
25 }
26 if(x==y&&a[2][1]==a[2][3]&&a[2][2]==a[2][4]){
27 printf("Yes!\n");
28 }
29 else{
30 printf("No!\n");
31 }
32 if(i%50==0)cout<<endl;
33 }
34 return 0;
35 }```
K
L [简单的分数](https://ac.nowcoder.com/acm/contest/322/L)
直接想到了GCD,也算是个模拟吧。
![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int T,op,a,b,c,d,e,f;
8 int gcd(int a,int b){
9 return b==0?a:gcd(b,a%b);
10 }
11 int main(){
12 cin>>T;
13 while(T--){
14 cin>>op>>a>>b>>c>>d;
15 if(op==1){
16 e=a*d+b*c;
17 f=b*d;
18 int k=gcd(e,f);
19 e/=k;
20 f/=k;
21 cout<<e<<'/'<<f<<endl;
22 }
23 else{
24 e=a*d-b*c;
25 f=b*d;
26 int kkkkk=0;
27 if(e<0){
28 e=-e;
29 kkkkk=1;
30 }
31 int k=gcd(e,f);
32 e/=k;
33 f/=k;
34 if(kkkkk==0) cout<<e<<'/'<<f<<endl;
35 else{
36 cout<<'-'<<e<<'/'<<f<<endl;
37 }
38 }
39 }
40 return 0;
41 }```
L
M HJ浇花
/*带的树状数组板子发现是坏的->_->
然后从左到右算改了N发还是不对。。。*/
emmmm没有啥树状数组,从左到右扫一遍看成爬山,用一个数组cnt[i]来统计在i位置向上还是向下,对于每组l,r,cnt[l]++,cnt[r+1]--,从0扫到max(r)+1,对于每个cnt[i]不为0的i,用i和上一个cnt不为0的位置和当前层数更新ans数组,然后更新当前层数。
```
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int n,cnt[1000020],last,now,rmx,ans[1000020];
5 int main(){
6 cin>>n;
7 int l,r;
8 for(int i=1;i<=n;i++){
9 scanf("%d%d",&l,&r);
10 rmx=max(rmx,r);
11 cnt[l]++;
12 cnt[r+1]--;
13 }
14 for(int i=0;i<=rmx+1;i++){
15 if(cnt[i]!=0){
16 ans[now]+=(i-last);
17 last=i;
18 now+=cnt[i];
19 }
20 }
21 cout<<ans[1];
22 for(int i=2;i<=n;i++){
23 printf(" %d",ans[i]);
24 }
25 return 0;
26 }```
M