首页 > 其他分享 >【补题】The 2022 SDUT Summer Trials

【补题】The 2022 SDUT Summer Trials

时间:2022-11-17 16:45:11浏览次数:73  
标签:Summer int 代码 Ginger maxn 补题 SDUT using include

比赛链接

The 2022 SDUT Summer Trials

A. Ginger's number

样例恶臭(恼)
签到题
简单分解因数就会发现要求的就是\(gcd\),直接算即可,时间复杂度\(\Theta(Tlog(max(x,y)))\)

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int gcd(int x,int y){
    if(x<y) swap(x,y);
    if(!y) return x;
    return gcd(y,x%y);
}
int main(){
    int i,j,n,m,x,y,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&x,&y);
        printf("%d\n",gcd(x,y));
    }
    // system("pause");
    return 0;
}

B. Ginger's game

简单题
很经典,用个单调栈维护每个数在哪段区间里是最小值即可。

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define maxn 200010
using namespace std;
ll a[maxn];
ll dp[maxn];
int st[maxn],top=0;
int main(){
    int i,j,n;
    ll ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%lld",&a[i]);
    for(i=1;i<=n;++i){
        while(top>0&&a[st[top]]>=a[i]) --top;
        dp[i]=dp[st[top]]+a[i]*(i-st[top]);
        st[++top]=i;
    }
    for(i=1;i<=n;++i) ans=max(ans,dp[i]);
    printf("%lld",ans);
    // system("pause");
    return 0;
}

C. Ginger's sequence

简单题

(但是我傻逼了)

不会真有人不会抽屉原理吧,不会吧不会吧_(但是我是傻逼睡前才发现,乐)

题目就是要求选取两个不同的非空子集,使得他们元素和相等\((模k意义下)\)。

那么\(n\)个元素,能组成的不同子集和共有\(2^n-1\)个(不包括空集),所以根据抽屉原理,大概只要有\(log_2(k)\)量级的\(n\)就能使得有两个子集和相同。

所以\(2^n-1>=k\)时我们直接输出"YES"。

\(2^n-1<k\)时暴力枚举子集即可,时间复杂度\(\Theta(k)\)。

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#define maxn 100010
using namespace std;
int a[maxn],dp[maxn];
int solve(){
    int n,k,i,j,m;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;++i) scanf("%d",&a[i]),a[i]%=k;
    for(m=0;(1<<m)<=k;++m);
    if(n>=m) return 1;
    for(i=1;i<(1<<n);++i){
        int sum=0;
        for(j=0;j<n;++j){
            if(i&(1<<j)) sum=(sum+a[j])%k;
        }
        dp[sum]++;
    }
    for(i=0;i<k;++i){
        if(dp[i]>1) return 1;
    }
    return 0;
}
int main(){
    int flag=solve();
    if(flag) printf("YES");
    else printf("NO");
    // system("pause");
    return 0;
}

D. Ginger's line

签到题
暴力判斜率是否相同即可。

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 5010
using namespace std;
int a[maxn],b[maxn];
int main(){
    int i,j,n,m,x,y,T;
    int ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d%d",&a[i],&b[i]);
    }
    for(i=1;i<=n;++i){
        for(j=i+1;j<=n;++j)
            ans+=(a[i]!=a[j]);
    }
    printf("%d",ans);
    // system("pause");
    return 0;
}

E. Ginger's coloring

签到题

沿着约束关系走就可以变成一个一个环(经典排列和置换套路),每个环的方案互相独立,计算相乘即可。

只有黑白两种颜色,更简单了,奇环\(0\),偶环\(2\)。(颜色多点还有点意思来着)

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define mod 998244353
#define maxn 200010
using namespace std;
int p[maxn],book[maxn];
int c[maxn],tot=0;
ll f(int x){
    return 2*((x^1)&1);
}
int main(){
    int i,j,n;
    ll ans=1;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&p[i]);
    for(i=1;i<=n;++i){
        if(book[i]) continue;
        int cnt=1;
        book[i]=1;
        for(j=p[i];j!=i;j=p[j]) cnt++,book[j]=1;
        c[++tot]=cnt;
    }
    for(i=1;i<=tot;++i){
        ans=(ans*f(c[i]))%mod;
    }
    printf("%lld",ans);
    // system("pause");
    return 0;
}

H. Ginger's clone

签到题

模拟即可。

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[210][210],book[210][210];
int t1=0,t2=0;
int b1[40001],b2[40001];
int n;
struct dir{
    int dx,dy;
    dir(){}
    dir(int t1,int t2){dx=t1,dy=t2;}
    void turn(){
        int t=-dy;
        dy=dx;
        dx=t;
    }
} dir1,dir2;
int nxt(int &x,int &y,dir &d){
    while(x+d.dx>n||x+d.dx<1||y+d.dy>n||y+d.dy<1||book[x+d.dx][y+d.dy]) d.turn();
    x=x+d.dx;y=y+d.dy;
    book[x][y]=1;
    return a[x][y];
}
int main(){
    int i,j;
    int x1,y1,x2,y2;
    scanf("%d",&n);
    x1=0,y1=1;x2=n+1,y2=n;
    dir1=dir(1,0),dir2=dir(-1,0);
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j) 
            scanf("%d",&a[i][j]);
    for(i=1;i<=n*n;++i){
        if(i&1) b1[++t1]=nxt(x1,y1,dir1);
        else b2[++t2]=nxt(x2,y2,dir2);
    }
    for(i=1;i<=t1;++i) printf("%d ",b1[i]);
    printf("\n");
    for(i=1;i<=t2;++i) printf("%d ",b2[i]);
    // system("pause");
    return 0;
}

I. Ginger's balance

简单题

做过小学智力题的应该都知道要尽量均分三份吧(

递归解比较方便。

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int f(int n,int m){
    if(m==1) return 0;
    if(m==2) return 1;
    int t;

    if((m+1)/3<=n) t=(m+1)/3;
    else t=n;
    return f(n,max(t,m-2*t))+1;
}
int main(){
    int i,j,n,m;
    scanf("%d%d",&n,&m);
    printf("%d",f(n,m));
    // system("pause");
    return 0;
}

J. Ginger's cow

简单题

裸的二分图最大匹配,跑匈牙利即可。

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define ll long long
#define maxn 200010
using namespace std;
char name[101][50];
int c=0;
int old[101];
int fst[101],nxt[1001],to[1001],cnt=0,visited[101];
int match[101];
int fd(char *p){
    for(int i=1;i<=c;++i){
        if(strcmp(p,name[i])==0) return i;
    }
    return 0;
}
void add(int x,int y){
    to[++cnt]=y;
    nxt[cnt]=fst[x];
    fst[x]=cnt;
}
int dfs(int x){
    visited[x]=1;
    for(int i=fst[x];i;i=nxt[i]){
        if(visited[match[to[i]]]) continue;
        if(!match[to[i]]||dfs(match[to[i]])){
            match[to[i]]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    int i,j,n,m,q;
    int ans=0,idx,idy;
    char x[50],y[50];
    scanf("%d%d%d",&m,&n,&q);
    for(i=1;i<=q;++i){
        scanf("%s",x);
        idx=fd(x);
        if(!idx) strcpy(name[idx=++c],x);
        old[idx]=1;
        scanf("%s",y);
        idy=fd(y);
        if(!idy) strcpy(name[idy=++c],y);
        add(idx,idy);
    }
    for(i=1;i<=n;++i){
        if(!old[i]) continue;
        for(j=1;j<=n;++j) visited[j]=0;
        ans+=dfs(i);
    }
    printf("%d",ans);
    // system("pause");
    return 0;
}

L. Ginger's function

简单题

模拟多项式乘法即可(甚至不需要\(FFT\))

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
struct item{
    int a,p;
    item(){}
    item(int x,int y){a=x,p=y;}
    bool operator <(item t){
        return p<t.p;
    }
};
vector<item> a,b,c,d;
int f[20];
void multi(){
    int i,j;
    c.clear();
    d.clear();
    for(i=0;i<a.size();++i){
        for(j=0;j<b.size();++j){
            c.push_back(item(a[i].a*b[j].a,a[i].p+b[j].p));
        }
    }
    sort(c.begin(),c.end());
    
    int sum=0;
    for(i=0;i<c.size();++i){
        if(i>0&&c[i].p>c[i-1].p&&sum){
            d.push_back(item(sum,c[i-1].p));
            sum=c[i].a;
        }
        else sum+=c[i].a;
    }
    if(sum) d.push_back(item(sum,c[c.size()-1].p));
    a.clear();
    for(i=0;i<d.size();++i){
        a.push_back(d[i]);
    }
}
int main(){
    int i,j,n,q,x;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;++i) scanf("%d",&f[i]);
    a.push_back(item(1,0));
    for(i=1;i<=n;++i){
        b.clear();
        b.push_back(item(1,0));
        b.push_back(item(-1,f[i]/2));
        b.push_back(item(-1,f[i]));
        multi();
    }
    sort(a.begin(),a.end());
    for(i=1;i<=q;++i){
        scanf("%d",&x);
        int pos=lower_bound(a.begin(),a.end(),item(1,x))-a.begin();
        printf("%d\n",a[pos].p==x?a[pos].a:0);
    }
    // system("pause");
    return 0;
}

总结

手速场,剩下几题还没写,之后如果能写出来再更吧(咕咕咕)

比区域赛坐牢舒服多了(bushi

标签:Summer,int,代码,Ginger,maxn,补题,SDUT,using,include
From: https://www.cnblogs.com/landmine-sweeper/p/16899954.html

相关文章

  • 绵阳2020CCPC补题
    绵阳2020CCPCD,K,J,L,GD.DefusetheBombs知识点:二分答案复杂度:\(O(nlogn+log^2n)\)vp时我猜了一个结论,验了几个样例就写了,喜提WA3然后队友写了二分答案复杂度\(O(......
  • codeforces补题计划
    11.15CodeforcesRound#833(Div.2)知识点:D:高位和对低位无影响E:笛卡尔树上dp补题传送门......
  • Codeforces Round #833 (Div. 2)补题
    CodeforcesRound#833(Div.2)D.ConstructOR知识点:高位和对低位无影响一开始以为和广州的M一样,是数位dp,后来发现只要找到一个就行果然无论什么时候都要看清题目......
  • 【补题】第 46 届 ICPC EC Final
    比赛题目:第46届ICPCECFinal(正式赛)榜单A.DFSOrder签到题容易发现对于一个点,它的最小位置就是从根走一条链直接到它,最大位置就是除了它的子树,其它全已经走过了。......
  • 广州2022CCPC补题
    IInfection知识点:树上背包第一次写树上背包的题目,没想到就是在区域赛中神奇的是树上背包的复杂度,看起来是\(O(n^3)\),但是实际计算只有\(O(n^2)\)学会树上背包后可......
  • Codeforces Round #786 (Div. 3) 补题记录
    小结:A,B,F切,C没写1ll对照样例才发现,E,G对照样例过,D对照样例+看了其他人代码(主要急于看后面的题,能调出来的但偷懒了。CF1674ANumberTransformation考虑若\(y\)......
  • CCPC2022威海补题
    K看完题之后思路是很自然的:对于每个要求,就转化成对于l和r的限制。原本被题目解释干扰了,纠结了一下区间长度的限制觉得很复杂;后来发现只要l和r合法,区间长度就合法,所以对于1......
  • 杭电多校补题
    题目100110021003100410051006100710081009101110121013​​Contest1​​Path​​Contest2​​\​​Contest3​​\\\​​Contest4​​\\\​​Contest5​​\\\​​Conte......
  • 骨牌铺方格 SDUT
      状态转移方程:dp[i]=dp[i-1]+dp[i-2]。当前行,可能是由上一行转移过来的,那么当前行就只能横着铺,所以方案数是dp[i-1]。当前行,可能是由i-2行转移过来的,那......
  • Team Extra Contest 2022-10-21补题
    D.38parrots线段树#include<bits/stdc++.h>usingnamespacestd;#defineIOSios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)#definerep(a,b......