第十七届浙大城市学院程序设计竞赛(同步赛)(ABFLC)

写了4题后注意力就没那么集中了，就感觉在划水一般~啊！！好菜啊我
A:Sumo and Keyboard-Cat;
题意：

思路：很显然就是求小写转大写或者大写变小写出现的次数。然后统计一下次数就行了，注意如果第一个字符是小写从1开始统计。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
    string s;cin>>s;
    int ans = 0;
    if(s[0] >= 'a' && s[0] <= 'z')ans = 1;
    for(int i = 0; i < s.size() - 1; i++){
        if(s[i] >= 'a' && s[i] <= 'z' && s[i + 1] >= 'A' && s[i + 1] <= 'Z')ans++;
        if(s[i] >= 'A' && s[i] <= 'Z' && s[i + 1] >= 'a' && s[i + 1] <= 'z')ans++;
    }
    cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
}

B:Sumo and His Followers
题意：

大概意思：有n个任务，每个任务有等待时间，问你怎么排使得平均等待时间最少。
思路：贪心让耗时最小的先执行就行了。排个序，然后扫一次就行。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
int a[maxn];
void solved(){
    int n;cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    sort(a + 1, a + 1 + n);
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        sum += a[i] * (n - i);
    } 
    printf("%.2lf\n",sum * 1.0 / n);
}
int main(){
    int t;cin>>t;
    while(t--)
    solved();
    return 0;
}

F:Sumo and Luxury Car
题意：

大概意思：就是说某人有n辆车，它可以从n辆车里面任意选x 个(x>0&&x<=n)，组成一个车队，然后再从这个车队任选一辆车自己用，问一共有多少种选法。
思路：
很容易发现要我们求的就是1 * C(n,1) + 2 * C(n,2) + 3 * C(n,3) + ... + n * C(n,n)
但是n比较大，迭代O(n)肯定会超时，所以要将公式化简。



然后快速幂跑一下就行了。
代码：

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int N = 2e5 + 10;
typedef long long int ll;
//1 * C(n,1) + 2 * C(n,2) + 3 * C(n,3) + ... + n * C(n,n)
//sigma k * C(n,k) = 2n^(n - 1) 
ll fastpow(ll a,ll b){
    ll res = 1;
    while(b){
        if(b & 1)res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
void solved(){
    ll n;cin>>n;
    cout<<n * fastpow(2,n - 1) % mod<<endl;
}
int main(){
    int t;cin>>t;
    while(t--)
    solved();
    return 0;
}

L:Sumo and Coins
题意：

大概意思：
你有n个硬币，其中a个正面朝上，b个反面朝下，你可以选择任意n-1个硬币翻转任意次，问能否翻转成全0或者全1.
思路：
这题我是猜，证明的话不太会。
我们用0表示正面朝上，1表示反面朝下。
首先考虑偶数。
当n=2,

无论a,b为多少都可以得到全0或者全1.
当n = 4;

无论a,b为多少都可以得到全0或者全1.
验证完这两个我就猜想n=2,应该输出all。
再考虑奇数
n = 3.

我们0的个数是奇数可以得到全0，0的个数是偶数可以得到全1，不妨再验证一个。
n = 5.

0的个数是奇数仍旧全0所以猜想应该是正确的，有大佬会严格的证明可以教教我~
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
    int n,a,b;cin>>n>>a>>b;
    if(n % 2 == 0){
        cout<<"ALL"<<endl;
    }else{
        if(a & 1)cout<<"UP"<<endl;
        else cout<<"DOWN"<<endl;
    }
}
int main(){
    int t;cin>>t;
    while(t--)
    solved();
    return 0;
}

C:Sumo and Virus
题意：

思路:模拟，a[i]:第i天已经感染的人数，b[i]:第i天预感染的人数。然后模拟。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 2e5 + 10;
ll a[maxn];//已感染
ll b[maxn];//预感染 
void solved(){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    ll x,m,n;cin>>x>>m>>n;
    ll c = 1;
    b[1] = 1;
    for(int i = 8; i <= n; i++){
        a[i] = b[i - 7] + a[i - 1];
        if(i >= 14)a[i] -= b[i - 13];
        if(x * a[i] <= m - c){
            b[i] = x * a[i];
        }else b[i] = m - c;
        c += b[i];
    }
    printf("%lld\n",a[n]);
}
int main(){
    int t;cin>>t;
    while(t--)
    solved();
    return 0;
}