第十七届浙大城市学院程序设计竞赛（同步赛）部分题解

签到题，在变换的时候+1

显然是贪心从小到大排序，之后求和

这题就是思维瞎搞题，首先想到的一点是七天前的是可以感染当天的，但是十三天前的不行，所以想到一个前缀和记录一下前i天感染的人数。

因此又想到可以设计一个数组表示第i天被感染几人，然后递推一下即可，这里还有一点是，当所有人都被感染了就没得感染了，判断一下即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
const int mod=1e9+7;
ll f[N];
ll s[N];
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        ll x,m,n;
        cin>>x>>m>>n;
        int i;
        memset(f,0,sizeof f);
        memset(s,0,sizeof s);
        f[1]=1;
        if(n<=7){
            cout<<0<<endl;
            continue;
        }
        if(n<=13){
            cout<<1<<endl;
            continue;
        }
        for(i=1;i<=n;i++){
            if(i>=8&&i<=13){
                int tmp;
                tmp=min(x*s[i-7],m-s[i-1]);
                f[i]=tmp;
            }
            else if(i>=14){
                f[i]=min(x*(s[i-7]-s[i-13]),m-s[i-1]);
            }
            s[i]=s[i-1]+f[i];
            if(s[i]>=m)
                break;
        }
        ll sum=0;
        for(i=n-7;i>=n-12;i--){
            sum+=f[i];
        }
        cout<<sum<<endl;
    }
}

View Code

这是一道数学题，首先a是斐波那契数列，如果知道数学通项就能秒了，就是一个等比数列求和

如果不知道数学通项，可以用高中常用的除某数之后相减的方法直接求得答案。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        ll k;
        sc("%lld", &k);
        ll ans1 = k, ans2 = k * k - k - 1;
        ll g = gcd(ans1, ans2);
        ans1 /= g;
        ans2 /= g;
        pr("%lld", ans1);
        if (ans2 != 1)
            pr("/%lld",ans2);
        pr("
");
    }
}

View Code

最简单的表达式很容易想到，问题就是求和怎么算，找第一项和最后一项，第二项和倒数第二项，运用常用的组合数对应相等的方式就能求得答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
const int mod=1e9+7;
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=(res%mod*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<n%mod*qmi(2,n-1)%mod<<endl;
    }
}

View Code

对于easy版本，因为只有一个点是-1，只要针对这个点所连的边即可，所有异或和最大，因此我们记录这些相邻的顶点的权值，计算每一位01个数，贪心求一下我们当前要选什么

因为每个位都不影响，这也是异或常见手法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
const int mod=1e9+7;
int h[N],ne[N],e[N],w[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
vector<int> num;
int g1[N],g2[N];
int id[32][2];
int sign[50];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i;
    int root;
    memset(h,-1,sizeof h);
    for(i=1;i<=n;i++){
        cin>>w[i];
        if(w[i]==-1){
            root=i;
        }
    }
    for(i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        g1[i]=a,g2[i]=b;
        add(a,b);
        add(b,a);
    }
    for(i=h[root];i!=-1;i=ne[i]){
        int j=e[i];
        num.push_back(w[j]);
    }
    for(i=0;i<num.size();i++){
        for(int j=0;j<31;j++){
            id[j][num[i]%2]++;
            num[i]/=2;
        }
    }
    ll res=0;
    int tmp=1;
    for(i=0;i<31;i++){
        if(id[i][0]>=id[i][1]){
            res+=0;
            tmp*=2;
        }
        else{
            res+=tmp;
            tmp*=2;
        }
    }
    w[root]=res;
    ll sum=0;
    res=0;
    for(i=1;i<=m;i++){
        res+=(w[g1[i]]^w[g2[i]]);
    }
    cout<<res<<endl;
    res=0;
    for(i=1;i<=n;i++){
        res+=w[i];
    }
    cout<<res<<endl;
}

View Code

这题手玩一下就能猜出答案，有些题虽然不会做，但是ac却没有问题，举几个例子，其实可以猜到肯定奇偶有关，因为题目信息很少。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
const int mod=1e9+7;
ll f[N];
ll s[N];
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n,a,b;
        cin>>n>>a>>b;
        if(n==1){
            if(a==0)
                cout<<"DOWN"<<endl;
            else
                cout<<"UP"<<endl;
            continue;
        }
        if(n%2==0){
            cout<<"ALL"<<endl;
        }
        else{
            if(a%2){
                cout<<"UP"<<endl;
            }
            else{
                cout<<"DOWN"<<endl;
            }
        }
    }
}

View Code