Gym 101972

F读错题wa了三个小时。自闭了，不然I题有可能能出的。。已经想到组合数也敲完组合数板子了。

A:这。。。**题吧，第一眼看的这个就秒了

 1 #include<bits/stdc++.h>
 2 #define pii pair<int,int>
 3 #define mk(a,b) make_pair(a,b)
 4 using namespace std;
 5 typedef long long ll;
 6 int a[11],b[11];
 7 void slove(int n,int id){
 8     if(id==1) {
 9         int k = 0;
10         while (n) {
11             k++;
12             a[k] = n % 10;
13             a[k]*=pow(10,k-1);
14             n /= 10;
15         }
16     } else{
17         int k = 0;
18         while (n) {
19             k++;
20             b[k] = n % 10;
21             b[k]*=pow(10,k-1);
22             n /= 10;
23         }
24     }
25 }
26 int t,x,y;
27 vector<pii>ans;
28 int main(){
29     ios::sync_with_stdio(false);
30     cin>>t;
31     while (t--){
32         memset(a,0, sizeof(a));
33         memset(b,0, sizeof(b));
34         ans.clear();
35         cin>>x>>y;
36         slove(x,1);
37         slove(y,2);
38         for(int i=1;i<=10;i++){
39             if(a[i]==0)
40                 continue;
41             for(int j=1;j<=10;j++){
42                 if(b[j]==0)
43                     continue;
44                 ans.push_back(mk(a[i],b[j]));
45             }
46         }
47         for(int i=0;i<ans.size();i++){
48             if(i==ans.size()-1){
49                 cout<<ans[i].first<<" x "<<ans[i].second<<endl;
50             } else{
51                 cout<<ans[i].first<<" x "<<ans[i].second<<" + ";
52             }
53         }
54     }
55 }

View Code

B：这篇写的很好 https://blog.csdn.net/lzc504603913/article/details/83863102

有几个关键的性质一定要注意到。

如果一个点有两颗儿子，那么这个点的祖先全部没有答案。

如果一个点有三个及以上儿子，这个点及这个点的祖先全部没有答案。

如果一个点没答案，他的所有祖先全没答案。

那么我们可以把点分为三类。1.没答案的 2. 一条链的 3. 两条链的(也就是这个点有两个儿子，然后这两个儿子是两条链，不然没答案嘛)

然后我们考虑题目要求满足的条件。

唔...那篇说的太好了我目前还想不到其他更好的表达方式了。。。复述一遍没有多大意义，请移步去看上面那个链接吧。

（我懒得敲等式什么的（大雾））

C：又卡cin。。。小学数学题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t;
 5 double a,b,c,x;
 6 int main(){
 7     //ios::sync_with_stdio(false);
 8     scanf("%d",&t);
 9     while (t--){
10         scanf("%lf%lf%lf%lf",&a,&b,&c,&x);
11         double ans = 0;
12         ans+=sqrt(a*a+(b+c+c)*(b+c+c));
13         x/=100;
14         ans += sqrt(b*b+a*a)*x;
15         ans+=sqrt((c+c+b*(1.0-x))*(c+c+b*(1.0-x))+a*(1.0-x)*a*(1.0-x));
16         printf("%.10f
",ans);
17     }
18 }

View Code

D：**

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t,n,x,y;
 5 int main(){
 6     ios::sync_with_stdio(false);
 7     cin>>t;
 8     while (t--){
 9         cin>>n>>x>>y;
10         if(n%2==0){
11             if(x>=n/2&&y>=n/2)
12                 cout<<"YES"<<endl;
13             else
14                 cout<<"NO"<<endl;
15         } else{
16             if(y>=n/2&&x>=n/2+1)
17                 cout<<"YES"<<endl;
18             else
19                 cout<<"NO"<<endl;
20         }
21     }
22 }

View Code

E：我做的很麻烦，可以不开那个数组，直接记录当前已知的最大测试数据就行

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t,k,n,m;
 5 char c[10005];
 6 int vis[10005];
 7 void slove(int st,int en){
 8     for(int i=st;i<=en;i++)
 9         vis[i]=(c[i]=='S');
10 }
11 int main(){
12     ios::sync_with_stdio(false);
13     cin>>t;
14     while (t--){
15         memset(vis,0, sizeof(vis));
16         memset(c,0, sizeof(c));
17         cin>>n>>m>>k;
18         for(int i=1;i<=n;i++)
19             cin>>c[i];
20         int mx = k;
21         slove(1,mx);
22         int ans = 0;
23         char op;int x;
24         while (m--){
25             cin>>op;
26             if(op=='A'){
27                 slove(mx+1,n);
28                 mx = n;
29             } else{
30                 cin>>x;
31                 if(x>mx){
32                     slove(mx+1,x);
33                     mx = x;
34                 } else{
35                     if(vis[x])
36                         ans++;
37                 }
38             }
39         }
40         cout<<ans<<endl;
41     }
42 }

View Code

F：我以为必须要全部用完，也就是“恰好”才可以。。。******************

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll a[27],t,s1,s2,minn,ans,sum;
 5 int main() {
 6     ios::sync_with_stdio(false);
 7     cin>>t;
 8     while(t--) {
 9         minn=1e12;
10         ans=s1=s2=sum=0;
11         for(int i=1;i<=26;i++) {
12             cin>>a[i];
13             if(a[i]==1)s1++;
14             if(a[i]>=2) {
15                 s2++;
16                 minn=min(a[i]/2,minn);
17             }
18         }
19         ans=s2*2;
20         if(s1>0) {
21             ans++;
22             sum=min(minn,s1);
23         }
24         else
25             sum=minn;
26         if(minn==1e12)sum=s1;
27         cout<<ans<<' '<<sum<<endl;
28     }
29     return 0;
30 }

View Code

G：从四个角分别维护一下然后枚举删掉的行列

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t,n,m;
 5 int a[505][505];
 6 int plu[505][505];
 7 int pru[505][505];
 8 int pld[505][505];
 9 int prd[505][505];
10 void init(){
11     memset(plu,0, sizeof(plu));
12     memset(pru,0, sizeof(pru));
13     memset(pld,0, sizeof(pld));
14     memset(prd,0, sizeof(prd));
15     memset(a,0, sizeof(a));
16 }
17 int main(){
18     ios::sync_with_stdio(false);
19     cin>>t;
20     while (t--) {
21         init();
22         cin >> n >> m;
23         for (int i = 1; i <= n; i++)
24             for (int j = 1; j <= m; j++)
25                 cin >> a[i][j];
26         for(int i=1;i<=n;i++){
27             for(int j=1;j<=m;j++){
28                 plu[i][j]=max(max(plu[i-1][j],plu[i][j-1]),a[i][j]);
29             }
30         }
31         for(int i=1;i<=n;i++){
32             for(int j=m;j>=1;j--){
33                 pru[i][j]=max(max(pru[i][j+1],pru[i-1][j]),a[i][j]);
34             }
35         }
36         for(int i=n;i>=1;i--){
37             for(int j=1;j<=m;j++){
38                 pld[i][j]=max(max(pld[i+1][j],pld[i][j-1]),a[i][j]);
39             }
40         }
41         for(int i=n;i>=1;i--){
42             for(int j=m;j>=1;j--){
43                 prd[i][j]=max(max(prd[i+1][j],prd[i][j+1]),a[i][j]);
44             }
45         }
46         int ans = 1e9+1;
47         for(int i=2;i<n;i++){
48             for(int j=2;j<m;j++){
49                 ans = min(ans,max(max(max(plu[i-1][j-1],prd[i+1][j+1]),pru[i-1][j+1]),pld[i+1][j-1])-min(min(min(plu[i-1][j-1],prd[i+1][j+1]),pru[i-1][j+1]),pld[i+1][j-1]));
50             }
51         }
52         cout<<ans<<endl;
53     }
54 }

View Code

H：暴力统计出来所有的字母对就行。我是直接维护个前缀

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t,n,m,k;
 5 string a,b;
 6 int pre[26];
 7 int cnt[26][26];
 8 int vis[26][26];
 9 int main(){
10     ios::sync_with_stdio(false);
11     cin>>t;
12     while (t--){
13         cin>>n>>m>>k>>a>>b;
14         a="*"+a;b="*"+b;
15         memset(pre,0, sizeof(pre));
16         memset(cnt,0, sizeof(cnt));
17         memset(vis,0, sizeof(vis));
18         for(int i=1;i<=m;i++){
19             pre[b[i]-'a']=pre[b[i]-'a']+1;
20             for(int j=0;j<26;j++){
21                 cnt[b[i]-'a'][j]+=pre[j];
22             }
23         }
24         int l=1,r=k;
25         ll ans = 0;
26         while (r<=n){
27             if(vis[a[r]-'a'][a[l]-'a']){}
28             else
29                 ans+=cnt[a[r]-'a'][a[l]-'a'],vis[a[r]-'a'][a[l]-'a']=1;
30             l++,r++;
31         }
32         cout<<ans<<endl;
33     }
34 }

View Code

I：锁的方案数猜也能猜出来。。。

考虑任选 m-1 个人，有C(n,m-1)种方案，每种方案都打不开，也就是都有至少一把锁是打不开的，所以锁最少是C(n,m-1)种。

对于钥匙，考虑先拿出来一个人，然后在n-1个人里选m-1个人，有C(n-1,m-1)种方案数，对于每种方案数，这个人都要有对应的钥匙，所以就是C(n-1,m-1)种方案数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod = 1e9+7;
 5 ll up[100005],inv[100005],down[100005];//down就是分子(分母*乘法逆元
 6 void init(){
 7     up[0]=1;
 8     for(int i=1;i<=100000;i++){
 9         up[i]=up[i-1]*i % mod;
10     }
11     inv[1]=1;//乘法逆元板纸，其实我也不懂...
12     for(int i=2;i<=100000;i++){
13         inv[i]=(mod-mod/i)*inv[mod%i]%mod;
14     }
15     down[0]=1;
16     for(int i=1;i<=100000;i++){
17         down[i]=down[i-1]*inv[i]%mod;
18     }
19 }
20 ll C(ll x,ll y){//组合数(逃...
21     return up[x]*down[y]%mod*down[x-y]%mod;
22 }
23 int t;
24 ll n,m;
25 int main(){
26     ios::sync_with_stdio(false);
27     init();
28     cin>>t;
29     while (t--){
30         cin>>n>>m;
31         cout<<C(n,m-1)<<" "<<C(n-1,m-1)<<endl;
32     }
33 }

View Code

J：遇见过，hdu上的好像是，问你杨辉三角第n行奇数的个数，这个是有规律的，一百度啥都有，就直接秒了

那个，，你要是看不出来这公式就是组合数就当我啥都没说。。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t;
 5 ll n;
 6 int main(){
 7     ios::sync_with_stdio(false);
 8     cin>>t;
 9     while (t--){
10         cin>>n;
11         int num = 0;
12         ll tmp = n;
13         while (n){
14             if(n&1)
15                 num++;
16             n>>=1;
17         }
18         cout<<((tmp+1)-(1ll<<num))<<endl;
19     }
20 }

View Code

K：一开始又看错了感觉奇难无比，但是A题那么**的题竟然人数跟K差不多，就重新看了下，，发现他这个只能按照顺序平移一位。。。

我一开始看成只要是能组成一个环就可以。。。然后头痛欲裂。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int na[26],nb[26];
 5 int t;
 6 string a,b;
 7 int main(){
 8     ios::sync_with_stdio(false);
 9     cin>>t;
10     while (t--){
11         memset(na,0, sizeof(na));
12         memset(nb,0, sizeof(nb));
13         int x;cin>>x;
14         cin>>a>>b;
15         string aa="",bb="";
16         for(int i=0;i<x;i++){
17             if(a[i]!=b[i]){
18                 aa+=a[i];
19                 bb+=b[i];
20             }
21         }
22         int n = aa.length();
23         int flag = 1;
24         for(int i=1;i<n;i++){
25             if(aa[i]!=bb[i-1]) {
26                 flag = 0;
27                 break;
28             }
29         }
30         if(aa[0]!=bb[n-1])
31             flag = 0;
32         if(flag)
33             cout<<"YES"<<endl;
34         else
35             cout<<"NO"<<endl;
36     }
37 }

View Code

这个B题感觉有点硬核，主要是我也没去想B题咋做。除此之外失误太多了。理论10题实际8题。。。另外3星场水题也太多了。。。说实话我们出的新生赛的那些水题都比大多数的三星场难很多。。。

滚回宿舍了。明天下午尽量快点做完计组实验然后去新生赛现场凑热闹嘿嘿嘿。