2017 Multi-University Training Contest 2

官方题解

1001 Is Derek lying?

找出上下界直接判断

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 char s1[100005];
 4 char s2[100005];
 5 int n,a,b,c,d;
 6 int main(){
 7     int t;
 8     scanf("%d",&t);
 9     while(t--){
10         a=0;
11         scanf("%d%d%d",&n,&c,&d);
12         scanf("%s%s",s1,s2);
13         for(int i=0;i<n;i++){
14             if(s1[i]==s2[i]) a++;
15         }
16         b=n-a;
17         int L=max(0,c-b),R=0;
18         if(a>c) R=c+b;
19         else R=n-(c-a);
20         if(d>=L&&d<=R){
21             printf("Not lying
");
22         }
23         else{
24             printf("Lying
");
25         }
26     }
27 
28 
29     return 0;
30 }
Psong

1002 hash

1003 Maximum Sequence

记录一个后缀最大值，贪心使每一个数最大。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int mod=1e9+7;
 4 int n;
 5 int a[500005];
 6 int b[500005];
 7 int suf[500005];
 8 int main(){
 9     while(scanf("%d",&n)!=EOF){
10         int ans=0;
11         memset(suf,0,sizeof(suf));
12         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
13         for(int i=1;i<=n;i++) scanf("%d",&b[i]);
14         sort(b+1,b+1+n);
15         for(int i=n;i>=1;i--) suf[i]=max(suf[i+1],a[i]-i);
16         ans=a[n+1]=suf[b[1]];
17         int now=a[n+1]-(n+1);
18         for(int i=n+2;i<=n*2;i++){
19             a[i]=max(suf[b[i-n]],now);
20             ans+=a[i]; ans%=mod;
21         }
22         printf("%d
",ans);
23     }
24 
25     return 0;
26 }
Psong

1004 Puzzle

性质一：数列交换相邻两个数，逆序对奇偶性改变。

性质二：以从左到右从上到下为顺序看作一个数列，不论如何改变最终逆序对奇偶性不变，因为空格总还是需要回到空格处，所以操作是会相互抵消。

性质三：最终一定可以得到除了右下角的2*2以外，全都满足位置要求。

求逆序对，判断奇偶。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL n,m,p;
 5 int main(){
 6     LL t;
 7     scanf("%lld",&t);
 8     while(t--){
 9         scanf("%lld%lld%lld",&n,&m,&p);
10         LL ans=0,tot=n*m-1;
11         while(tot>p){
12             LL tmp=(tot+p-1)/p;
13             LL last=(tmp-1)*(p-1);
14             ans+=last*tmp/2;
15             tot-=tmp;
16         }
17         if(ans%2==0) printf("YES
");
18         else printf("NO
");
19     }
20 
21     return 0;
22 }
Psong

1005 Sdjpx Is Happy

1006 Funny Function

f[1][n]的通项可以求出，再向后计算可得f[m][1]的公式。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL mod=1e9+7;
 5 LL pow_mod(LL a,LL n){
 6     LL res=1,t=a;
 7     while(n){
 8         if(n&1) res=(res*t)%mod;
 9         t=(t*t)%mod;
10         n/=2;
11     }
12     return res;
13 }
14 LL inv(LL x){
15     return pow_mod(x,mod-2);
16 }
17 LL n,m;
18 int main(){
19     LL t;
20     cin>>t;
21     while(t--){
22         cin>>n>>m;
23         LL ans1=pow_mod(2,m)*pow_mod( (pow_mod(2,n)-1+mod)%mod,m-1 )%mod;
24         LL ans2=pow_mod(-1,m)*pow_mod( (pow_mod(-1,n)-1+mod)%mod,m-1 )%mod;
25         LL ans=(ans1-ans2+mod)%mod;
26         ans=ans*inv((3*pow_mod(2,m-1))%mod)%mod;
27         cout<<ans<<endl;
28     }
29 
30     return 0;
31 }
Psong

1007 If the starlight never fade

1.原根：假设一个数g是P的原根，那么g^i mod P的结果两两不同,且有 1<g<P, 0<i<P,归根到底就是g^(P-1) = 1 (mod P)当且仅当指数为P-1的时候成立.(这里P是素数)。

2.所有的数在取模的情况下都可以由原根的幂次表示，当模为1时，幂次为 p-1。

3.若 gcd(n,i)=1 则 gcd(n,n-i)=1。

4.由3可推出：[1,n]中与n互质的数的和为 phi(n)*n/2。

官方题解推导（对于每一个y，x的取值个数相同）：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL mod=1e9+7;
 5 LL euler(LL n){
 6     LL ans=n;
 7     for(LL i=2;i*i<=n;i++){
 8         if(n%i==0){
 9             ans-=ans/i;
10             while(n%i==0) n/=i;
11         }
12     }
13     if(n>1) ans-=ans/n;
14     return ans;
15 }
16 LL m,p,tmp;
17 void add(LL &x,LL y){
18     x%=mod; y%=mod;
19     x=(x+y)%mod;
20     if(x<0) x+=mod;
21 }
22 LL fun(LL x){
23     if(x==1) return 1;
24     else return (x*euler(x)/2)%mod;
25 }
26 int main(){
27     LL t;
28     scanf("%lld",&t);
29     LL T=t;
30     while(t--){
31         scanf("%lld%lld",&m,&p);
32         LL ans=0;
33         add(ans,-(p*(p-1)/2%mod));
34         for(int i=1;i*i<=p-1;i++){
35             if((p-1)%i==0){
36                 tmp=i;
37                 add(ans,(tmp*tmp%mod)*fun((p-1)/tmp));
38                 if(i*i!=p-1){
39                     tmp=(p-1)/i;
40                     add(ans,(tmp*tmp%mod)*fun((p-1)/tmp));
41                 }
42             }
43         }
44         printf("Case #%lld: %lld
",T-t,ans*m%mod);
45     }
46 
47     return 0;
48 }
Psong

1008 To my boyfriend

每个数分开计算期望再求和。

总数小于13的容斥，大于13的枚举不存在的情况。

（13=log1e4）使得时间复杂度最小。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL n,m;
 5 LL a[105][105];
 6 vector<LL> pp[10005][105];
 7 vector<LL> num;
 8 struct node{
 9     LL x,y;
10 };
11 vector<node> poLL[10005];
12 LL solve(LL u){
13     LL res=0;
14     for(LL i=1;i<=n;i++)
15     for(LL j=1;j<=m;j++){
16         if(a[i][j]==u) continue;
17         LL ry=m+1;
18         for(int k=i;k<=n;k++){
19             for(int q=0;q<pp[u][k].size();q++){
20                 if(pp[u][k][q]>=j) {
21                     ry=min(ry,pp[u][k][q]);
22                     break;
23                 }
24             }
25             res+=ry-j;
26         }
27     }
28     return res;
29 }
30 LL vis[20];
31 void dfs(LL deep,LL u,LL times,LL &res){
32     if(deep>=poLL[u].size()){
33         if(times==0) return;
34         LL lx=105,ly=105,rx=0,ry=0;
35         for(LL i=0;i<poLL[u].size();i++){
36             if(vis[i]){
37                 lx=min(lx,poLL[u][i].x);
38                 ly=min(ly,poLL[u][i].y);
39                 rx=max(rx,poLL[u][i].x);
40                 ry=max(ry,poLL[u][i].y);
41             }
42         }
43         if(times%2==1) res+=(n-rx+1)*lx*(m-ry+1)*ly;
44         else res-=(n-rx+1)*lx*(m-ry+1)*ly;
45     }
46     else{
47         vis[deep]=1;
48         dfs(deep+1,u,times+1,res);
49         vis[deep]=0;
50         dfs(deep+1,u,times,res);
51     }
52 }
53 int main(){
54     LL t;
55     scanf("%lld",&t);
56     while(t--){
57         num.clear();
58         scanf("%lld%lld",&n,&m);
59         for(LL i=0;i<=n*m;i++){
60             poLL[i].clear();
61             for(int j=1;j<=n;j++) pp[i][j].clear();
62         }
63         for(LL i=1;i<=n;i++)
64         for(LL j=1;j<=m;j++){
65             scanf("%lld",&a[i][j]);
66             num.push_back(a[i][j]);
67             poLL[a[i][j]].push_back((node){i,j});
68             pp[a[i][j]][i].push_back(j);
69         }
70         sort(num.begin(),num.end());
71         num.erase(unique(num.begin(),num.end()),num.end());
72         LL ans=0;
73         LL tot=(n*(n+1)/2)*(m*(m+1)/2);
74         for(LL i=0;i<num.size();i++){
75             LL v=num[i];
76             if(poLL[v].size()<=13){
77                 memset(vis,0,sizeof(vis));
78                 LL tmp=0;
79                 dfs(0,v,0,tmp);
80                 ans+=tmp;
81             }
82             else ans+=tot-solve(v);
83         }
84         printf("%.9lf
",(double)ans/tot);
85     }
86     return 0;
87 }
Psong

1009 TrickGCD

每一个区间gcd不为1，只要[1,n]的gcd不为1就好。

记录每一个数出现的次数维护前缀和，求出当gcd为每个数的倍数时的总数。

最后需要去重。

（题解给的是莫比乌斯变换）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL mod=1e9+7;
 5 LL n;
 6 LL a[100005];
 7 LL x[100005];
 8 LL sum[100005];
 9 LL num[100005];
10 LL pow_mod(LL a,LL n){
11     LL res=1,t=a;
12     while(n){
13         if(n&1) res=(res*t)%mod;
14         t=(t*t)%mod;
15         n/=2;
16     }
17     return res;
18 }
19 LL solve(LL x,LL min_num){
20     LL res=1;
21     LL tmp=min_num/x;
22     while(tmp--){
23         LL num=sum[min(x*(tmp+2)-1,100001LL)]-sum[min(x*(tmp+1)-1,100000LL)];
24         if(num==0) continue;
25         res=(res*pow_mod(tmp+1,num))%mod;
26     }
27     return res;
28 }
29 int main(){
30     LL t;
31     scanf("%lld",&t);
32     LL T=t;
33     while(t--){
34         memset(num,0,sizeof(num));
35         memset(sum,0,sizeof(sum));
36         memset(x,0,sizeof(x));
37         scanf("%lld",&n);
38         LL L=100005,R=0;
39         for(LL i=1;i<=n;i++){
40             scanf("%lld",&a[i]); num[a[i]]++;
41             L=min(L,a[i]); R=max(R,a[i]);
42         }
43         for(LL i=1;i<=100003;i++) sum[i]=sum[i-1]+num[i];
44         for(LL i=2;i<=L;i++) x[i]=solve(i,R);
45         for(LL i=L;i>=2;i--){
46             for(LL j=i+i;j<=L;j+=i){
47                 x[i]=(x[i]-x[j]+mod)%mod;
48             }
49         }
50         LL ans=0;
51         for(int i=1;i<=L;i++) ans=(ans+x[i])%mod;
52 
53         printf("Case #%lld: %lld
",T-t,ans);
54     }
55 
56     return 0;
57 }
Psong

1010 String and String

1011 Regular polygon

整点中只存在正四边形。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int x[2005],y[2005];
 5 int vis[2005][2005];
 6 int main(){
 7     while(~scanf("%d",&n)){
 8         memset(vis,0,sizeof(vis));
 9         for(int i=1;i<=n;i++){
10             scanf("%d%d",&x[i],&y[i]);
11             x[i]+=500; y[i]+=500;
12             vis[x[i]][y[i]]=1;
13         }
14         int ans=0;
15         for(int i=1;i<=n;i++){
16             for(int j=i+1;j<=n;j++){
17                 int dx=x[i]-x[j];
18                 int dy=y[i]-y[j];
19                 if(vis[x[i]+dy][y[i]-dx]&&vis[x[j]+dy][y[j]-dx]) ans++;
20                 if(vis[x[i]-dy][y[i]+dx]&&vis[x[j]-dy][y[j]+dx]) ans++;
21             }
22         }
23         printf("%d
",ans/4);
24     }
25 
26     return 0;
27 }
Psong
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/N-Psong/p/7252046.html