“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛(2020-5-10)

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

地址：https://ac.nowcoder.com/acm/contest/5477#question

A 张老师和菜哭武的游戏

1到n中，如果p能被拿走，则一定满足p=x*a+y*b，所以p一定是a，b最小公因数的倍数，所以最后判断奇偶即可

 1 #include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<vector>
 4 #include<queue>
 5 #include<string>
 6 #include<list>
 7 #include<set>
 8 #include<map>
 9 #include<stack>
10 # define PI 3.14159265358979323846
11 using namespace std;
12 typedef long long ll;
13 const int maxn = 2e5+10;
14 const int mod = 11092019;
15 int main()
16 {
17     int t;
18     cin>>t;
19     while(t--)
20     {
21         int n,a,b;
22         cin>>n>>a>>b;
23         int f = n/__gcd(a,b);
24         if(f%2==0) cout<<"No"<<endl;
25         else cout<<"Yes"<<endl;
26     }
27     return 0;
28 }

B 伤害计算

以“+”号分割字符串，分为两类:含有d和没有d，注意：最好全程都用int，最后/2；

输出浮点数的时候，如果有1000000之类的数可能会输出成1e+06的形式

 1 #include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<vector>
 4 #include<queue>
 5 #include<string>
 6 #include<list>
 7 #include<set>
 8 #include<map>
 9 #include<stack>
10 # define PI 3.14159265358979323846
11 using namespace std;
12 typedef long long ll;
13 const int maxn = 2e5+10;
14 const int mod = 11092019;
15 int main()
16 {
17     vector<string> v;
18     string s;
19     cin>>s;
20     string t;
21     for(int i=0;i<s.length();i++)
22     {
23         if(s[i]!='+')
24         {
25             t+=s[i];
26         }
27         else
28         {
29             v.push_back(t);
30             t.clear();
31         }
32         if(i==s.length()-1) v.push_back(t);
33     }
34     
35     
36 //    for(auto it=v.begin();it!=v.end();it++){
37 //        cout<<*it<<endl;
38 //    }
39     
40     
41     int sum1 = 0;
42     int sum2 = 0;
43     for(auto it=v.begin();it!=v.end();it++)
44     {
45         string x = *it;
46         if(x.find('d')!=x.npos)
47         {
48             int a=0,b=0;
49             int i=0;
50             for(i;i<x.length();i++)
51             {
52                 if(x[i]!='d')
53                 {
54                     a = a*10+(x[i]-'0');
55                 }
56                 else
57                 {
58                     i++;
59                     break;
60                 }
61             }
62             for(i;i<x.length();i++)
63             {
64                 b = b*10+(x[i]-'0');
65             }
66 //            cout<<a<<" "<<b<<endl;
67             sum1+=a*(b+1);
68         }
69         else
70         {
71             int p = 0;
72             for(int i=0;i<x.length();i++)
73             {
74                 p = p*10+(x[i]-'0');
75             }
76 //            cout<<p<<endl; 
77 //                     为了使用int，现加双份，最后/2
78             sum2 += p+p;
79             
80         }
81     }
82     int sum = sum1+sum2;
83     if(sum%2==0) cout<<sum/2<<endl;
84     else cout<<sum/2<<".5"<<endl;
85     return 0;
86 }

F 排列计算

知识点：差分前缀和；

前缀和：就是一个数组，要快速静态查询区间和，我们只要处理一个数组时A[i]=a[1]+a[2]+...+a[i].

那么查询区间[l,r]的时候只要输出A[r]-A[l-1].

差分数组：多次在给定数组的某区间加上某数，使用差分数组可以加快运算速度。

 1 #include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<vector>
 4 #include<queue>
 5 #include<string>
 6 #include<list>
 7 #include<set>
 8 #include<map>
 9 #include<stack>
10 # define PI 3.14159265358979323846
11 using namespace std;
12 typedef long long ll;
13 const int maxn = 2e5+10;
14 const int mod = 11092019;
15 int main()
16 {
17     ll node[maxn]={0};
18     ll n,m;
19     cin>>n>>m;
20     while(m--)
21     {
22         ll a,b;
23         cin>>a>>b;
24         node[a]++;
25         node[b+1]--;
26     }
27     for(ll i=1;i<=n;i++)
28     {
29         node[i]+=node[i-1];
30     }
31     sort(node+1,node+n+1);
32     ll x = 1;
33     ll ans = 0;
34     for(ll i=1;i<=n;i++)
35     {
36         ans+=node[i]*x;
37         x++;
38     }
39     cout<<ans<<endl;
40     return 0;
41 }