2019吉林省赛

A.

题意：已知$a,b,c,k$，每次操作为：

1.If a>b then a = a - b.
2.If b>c then b = b - c.
3.If c>a then c = c - a.

操作k次后，询问最终的$a,b,c$为多少？

分析：暴力模拟即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;scanf("%d",&t);
    int x,y,z,k;
    while (t--){
        scanf("%d%d%d%d",&x,&y,&z,&k);
        while (k>0){
            if(x==y && y==z) break;
            if (x>y) x-=y;
            if (y>z) y-=z;
            if (z>x) z-=x;
            k--;
        }
        printf("%d %d %d
",x,y,z);
    }
    return 0;
}

B.

题意：已知一棵n个结点的树，首先有以下两个定义：

　　礼物边：不存在相邻边与他颜色相同。

　　礼物点：在某一棵树内，从x点开始的路径均为礼物边。

每次询问x，即以x为根的子树内礼物节点的个数为多少。

分析：

　　比赛的时候题意一直读不通（事实上是，赛场后题意也读不懂。至今和队友还是有题意纠结？？？但是两份代码都过了？？数据是真的水。

考虑每次询问x时，有这样两种情况是不满足定义的：

　　1. 父亲到x与x到儿子的颜色相同。这种情况下，对于以父亲为根的子树内，父亲本身是不满足题意要求的。

　　2. 点x存在去往两个儿子的边颜色相同。这种情况下，我们不再需要考虑对于这两个儿子子树对于答案的贡献，可以直接无视这两个儿子子树了。

代码：（来自xjb大佬，我写了一份假代码。我hacak我自己.jpg

#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define P pair<int,int>
using namespace std;
int n,l,r,c,x,f[N];
vector<P>G[N];
int dfs(int x,int fa,int lstc){
    f[x]=1;
    int num=0,num1=0;
    map<int,int>mp;
    for(auto u:G[x])
    if(u.first!=fa){        
        int tmp=dfs(u.first,x,u.second);
        if(mp.find(u.second)!=mp.end()) mp[u.second]=0;else mp[u.second]=tmp;
        if(u.second==lstc) f[fa]=0;
    }
    for(auto u:mp){
        num+=u.second;
        if(u.first!=lstc) num1+=u.second;
    }
    num1+=f[x];
    f[x]+=num;
    return num1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&l,&r,&c);
        G[l].push_back(P(r,c));
        G[r].push_back(P(l,c));
    }
    dfs(1,-1,-1);
    int Q;
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&x);
        printf("%d
",f[x]);
    }
}

另：指路队友博客题解：dfs序+差分。https://blog.csdn.net/qq_43813163/article/details/95348450

D.

题意：已知一棵n个节点的树，对于任一一个点集S，询问答案$sum_{ssubset S}f(s)$。其中对于$f(s)$的定义为：$f(s)=a[LCA(S)] (s 非空)$。

分析：题意可以变为对于每一个结点x，他对于整个题答案的贡献为多少，即他出现在了多少个集合之中。考虑每一个点的时候，考虑x作为一个集合S的LCA出现的次数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const ll mod=1e9+7;
vector<int> mp[maxn];
int sz[maxn],a[maxn];
ll ans;
ll pow_(int x,int y){
    ll res=1ll,base=1ll*x;
    while (y){
        if (y&1) (res*=base)%=mod;
        (base*=base)%=mod;
        y>>=1;
    }
    return res;
}
void dfs(int x,int fa){
    ll num=0;
    for (int i=0;i<mp[x].size();i++){
        if (mp[x][i]==fa) continue;
        dfs(mp[x][i],x);
        sz[x]+=sz[mp[x][i]];
        ll kk=pow_(2,sz[mp[x][i]]);
        (num+=kk-1+mod)%=mod; 
    }
    sz[x]++;
    ll tmp=(pow_(2,sz[x])-1-num+mod)%mod;
    (ans+=(1ll*a[x]*tmp))%=mod;
}

int main(){
    int n,x,y;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),sz[i]=0;
    for (int i=0;i<n-1;i++){
        scanf("%d%d",&x,&y);
        mp[x].push_back(y);
        mp[y].push_back(x);
    }
    mp[1].push_back(0);
    ans=0;
    dfs(1,0);
    printf("%lld
",ans);
    return 0;
}

E.

题意：用火柴棒拼接小正方形，问拼成n个小正方形所需要的最少木棍数为多少？

分析：找规律题。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(ll n){
    ll tmp=sqrt(n);
    if (tmp*tmp==n) return (n+tmp)*2;
    ll m=(tmp+1)*(tmp+1);
    ll len=m-tmp*tmp-1;
    ll res=0;
    if (tmp*tmp+len/2>=n){
        res+=2*(tmp+tmp*tmp);
        res+=(n-tmp*tmp)*2+1;
    }
    else{
        res+=2*(tmp+tmp*tmp);
        res+=(n-tmp*tmp)*2+2;
    }
    return res;
}
int main(){
    int t; scanf("%d",&t);
    ll n;
    while (t--){
        scanf("%lld",&n);
        ll ans=solve(n);
        printf("%lld
",ans);
    }
    return 0;
} 

F.

题意：已知一张图$dis[n][n]$，其中$dis[i][j]$代表两点之间的“最短路”。重新构建一张新图，问最少保留几条边可以满足两点之间路径最短。

分析：floyd过程中不断去松弛两点间的最短路，如果可松弛，那么原来存的边就可以不保留。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
const int inf=0xfffffff;
int a[maxn][maxn],vis[maxn][maxn];
int main(){
    int n;scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            vis[i][j]=1;
        }
    int ans=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (i==j) continue;
            for (int k=1;k<=n;k++){
                if (j==k || i==k) continue;
                if (a[i][k]+a[k][j]<=a[i][j]){
                    vis[i][j]=0;vis[j][i]=0;
                    a[i][j]=a[i][k]+a[k][j];
                }
            }
        }
    } 
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) if (!vis[i][j]) ans++;
    printf("%d
",(n*n-ans-n)/2);
    return 0;
} 

G.

题意：已知两点$s,e$，有一束光线从s开始指向e，询问是否点$(px,py)$在这束光线上。

分析：判断点在射线上。

代码：

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    return 1;
}
int main(){
    int t; scanf("%d",&t);
    double sx,sy,ex,ey,px,py;
    while (t--){
        scanf("%lf%lf%lf%lf",&sx,&sy,&ex,&ey);
        scanf("%lf%lf",&px,&py);
        if (sgn(ex-sx)==sgn(sx-px) && sgn(ey-sy)==sgn(sy-py)){
            printf("NO
");
            continue;
        }
        if (sx==ex){
            if (px==sx) printf("YES
");
            else printf("NO
");
            continue;
        }
        if (sy==ey){
            if (py==sy) printf("YES
");
            else printf("NO
");
            continue;
        }
        double k=(sy-ey)/(sx-ex);
        double b=sy-k*sx;
        double tmp=k*px+b;
        if (sgn(tmp-py)==0) printf("YES
");
        else printf("NO
");
    }
    return 0;
} 

H.

题意：有n个“up"，m个"down"，构造一个序列，要求每一点处的"up"数量$geq$"down"数量。同时，还需要挑选k个时间添加背景音乐。询问总的方案数为多少?答案需要%(1e5+3)。

分析：卡特兰数应用。（我也不知道怎么推。但这个题和hdoj1133基本一样。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e5+3;
const int N=1e5+3;
typedef long long ll;
ll fac[N],inv_fac[N];
ll qpow(ll a,ll b){
    ll ret=1,tmp=a;
    while(b){
        if(b&1) (ret*=tmp)%=mod;
        b/=2;
        (tmp*=tmp)%=mod;
    }
    return ret;
}
void init(){
    fac[0]=1;
    for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
    inv_fac[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--) inv_fac[i]=inv_fac[i+1]*(i+1)%mod;
}
ll C(int n,int m){
    return (fac[n]*inv_fac[n-m]%mod)*inv_fac[m]%mod;
}
ll Lucas(int n,int m)
{
    if(m>n) return 0;
    ll ret=1;
    while(m>0LL){
        ret=(ret*C(n%mod,m%mod))%mod;
        m/=mod;
        n/=mod;
    }   
    return ret;
}
int main(){
    init();
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    int ans=Lucas(n+m,n)-Lucas(n+m,n+1);
    ans=1ll*ans*Lucas(n+m,k)%mod;
    printf("%d
",ans);    
    return 0;
}

I.

题意：convert all “ig”, “IG” and “Ig” including in the string to “iG”.

分析：模拟。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int len=s.size();
    for (int i=0;i<len-1;i++){
        if ((s[i]=='i' || s[i]=='I') && (s[i+1]=='g' || s[i+1]=='G')){
            s[i]='i'; s[i+1]='G';
        }
    }
    cout << s << endl;
    return 0;
} 

J.

题意：求公式：$[cos^2(frac{(n+1)!+1)}{n}astpi)]$。$2le nle 1e9$

分析：打表找规律。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int check(int n){
    int kk=sqrt(n);
    for(int i=2;i<=kk;i++){
        if (n%i==0) return false;
    } 
    return true;
}
int main(){
    int t;scanf("%d",&t);
    int n;
    while(t--){
        scanf("%d",&n);
        if (check(n)) printf("1
");
        else printf("0
");
    }
    return 0;
}