Wannafly Winter Camp 2020-Day1

wenzhuan

发布于 2022-08-15 12:21:14

2690

发布于 2022-08-15 12:21:14

第一场比赛还算比较顺利8

队伍BCH三题 rk55 我写了CH两题算是没丢数学选手兼Java选手的脸吧233 开题时看到H的题目“最大公约数”就直接点进去了然后有思路开始写 wa2 造了几个小数据发现自己有地方假了调过了一交还是wa2 然后想了想极限数据啊好像long long必炸就换Java写了然后AC 在我调H的时候队友已经把B过了然后好像是对着F自闭？ H过了惊闻刘老师把C秒了我:刘老师能秒我们应该也能A! 就看看C 很快有了想法手推了一下样例验证了猜想开始写因为我是没有化出式子的QAQ 就一堆中间过程写得头都没了写完一测样例四个没过开始自闭然后当时以为五点半就结束了有点想放弃了一看比赛时间还一个小时又充满了信心继续调终于把第四个样例调对了一比对第五个样例的对的直接交了 1A 激动得要死最后45min试着想F 实在是没思路QAQ 比赛结束! 晚上听jls讲题啊jls真的太帅了我永远喜欢jry 附赛时代码

2020 CCPC Wannafly Winter Camp Day1 B. 密码学

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
char s[1005][105];
int n,m,x[1005],y[1005];
int change(char c){
    if(c>='a') return c-'a'; else return c-'A'+26;
}
void solve(int a,int b){
    int l1=strlen(s[a]),l2=strlen(s[b]); rep(i,0,l2){
        int p=change(s[a][i%l1]),q=change(s[b][i]),t=(q-p+52)%52;
        if(t<26) s[b][i]='a'+t; else s[b][i]='A'+t-26;
    }
}
int main(){
    sc(n); sc(m); rep(i,1,m+1) sc(x[i]),sc(y[i]);
    rep(i,1,n+1) scs(s[i]); dep(i,m,1) solve(x[i],y[i]);
    rep(i,1,n+1) pf("%s\n",s[i]);
}

2020 CCPC Wannafly Winter Camp Day1 C. 染色图

想了想公式确实是可以化出来的但我没有( 调傻了(

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int main(){
    int _; sc(_); while(_--){
        ll n,l,r; scl(n); scl(l); scl(r);
        ll ans=n*(n-1)/2%mod,res=0; ans=ans*(r-l+1)%mod;
        for(ll i=1;i*i<=n;i++){
            ll r1=n/i,l1=n/(i+1)+1;
            if(l1>r1) l1=r1; //上下界 
            if(i>=l){
                ll ys=n%i,sy=i-ys; //余数 剩余 
                res+=ys*(r1*(r1+1)/2)%mod+sy*(r1*(r1-1)/2)%mod;
                res%=mod; //i时的数量
            }
            if(r1==i) break;
            l1=max(l1,l); r1=min(r1,r);
            if(l1>r1) continue;
            ll a1=n%r1,a2=n%l1;
            ll num=(r1-l1+1),sum=(a1+a2)*num/2%mod;
            ll rem=(l1+r1)*num/2-sum; rem%=mod;
            ll t1=i*(i-1)/2%mod,t2=i*(i+1)/2%mod; 
            res+=t1*rem%mod; res%=mod;
            res+=t2*sum%mod; res%=mod;
        } ans-=res; ans=(ans+mod)%mod;
        pf("%lld\n",ans);
    }
}

2020 CCPC Wannafly Winter Camp Day1 H. 最大公约数

wa了两次才想到用Java(

import java.math.*;
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt(); while(t-->0){
            int n=sc.nextInt(); int x=sc.nextInt();
            int[] vis=new int[505];
            for(int i=1;i<=n;i++) vis[i]=0;
            if(n<2*x) Syst,em.out.println(x);
            else{
                for(int i=2*x;i<=n;i+=x) vis[i]=1;
                for(int i=2*x;i<=n;i+=x) for(int j=i*2;j<=n;j+=i) if(vis[j]==1) vis[j]=0;
                BigInteger ans=BigInteger.valueOf(x); ans=ans.multiply(new BigInteger("2"));
                for(int i=2*x+1;i<=n;i++) if(vis[i]==1){
                    BigInteger tmp=BigInteger.valueOf(i);
                    tmp=tmp.divide(ans.gcd(BigInteger.valueOf(i)));
                    ans=ans.multiply(tmp);
                } System.out.println(ans);
            }
        }
    }
}

补题:

2020 CCPC Wannafly Winter Camp Day1 A. 期望逆序对

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e3 + 5;
const int mod = 998244353;
pii p[maxn];
ll inv[maxn];
int cmp(pii a,pii b){
    return a.first+a.second<b.first+b.second;
}
ll qpow(ll a,ll b){
    ll ans=1; while(b){
        if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod;
    } return ans;
}
ll count(pii a,pii b){
    if(b.first>a.second) return 0;
    int l=max(a.first,b.first),r=min(a.second,b.second);
    ll ans=1ll*(l-b.first+r-b.first)*(r-l+1)/2%mod;
    ans=(ans+1ll*(a.second-r)*(b.second-b.first+1))%mod;
    return ans;
}
int main(){
    int n; sc(n); rep(i,0,n) sc(p[i].first),sc(p[i].second); sort(p,p+n,cmp); 
    rep(i,0,n) inv[i]=qpow(p[i].second-p[i].first+1,mod-2);
    ll ans(0); rep(i,0,n) rep(j,i+1,n) ans=(ans+inv[i]*inv[j]%mod*count(p[i],p[j])%mod)%mod;
    pf("%lld\n",ans);
}

2020 CCPC Wannafly Winter Camp Day1 F. 乘法

生涯之耻

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
ll n,m,k,a[maxn],b[maxn],an[3],bn[3];
ll getsum(ll c,ll x){
    int l=1,r=m; while(l<=r){
        int mid=(l+r)/2;
        if(b[mid]*c>=x) c>0?r=mid-1:l=mid+1;
        else c>0?l=mid+1:r=mid-1;
    } return c>0?m-l+1:r;
}
int check(ll x){
    ll sum(0); rep(i,1,n+1) sum+=getsum(a[i],x);
    return sum>=k;
}
ll solve(ll l,ll r){
    while(l<=r){
        ll mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    } return r;
}
int main(){
    scl(n); scl(m); scl(k);
    rep(i,1,n+1) scl(a[i]),an[a[i]?a[i]>0?0:1:2]++;
    rep(i,1,m+1) scl(b[i]),bn[b[i]?b[i]>0?0:1:2]++;
    sort(a+1,a+n+1); sort(b+1,b+m+1);
    ll t=an[0]*bn[0]+an[1]*bn[1];
    if(k<=t) return pf("%lld\n",solve(1ll,max(a[1]*b[1],a[n]*b[m]))),0;
    t+=an[2]*m+bn[2]*n-an[2]*bn[2]; if(k<=t) return puts("0"),0;
    return pf("%lld\n",solve(min(a[1]*b[m],b[1]*a[n]),-1ll)),0;
}

2020 CCPC Wannafly Winter Camp Day1 I. K小数查询

namo n2可以过

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
int a[maxn],p[maxn];
int main(){
    int n,m; sc(n); sc(m); rep(i,1,n+1) sc(a[i]); while(m--){
        int op,l,r,x; sc(op); sc(l); sc(r); sc(x);
        if(op==1) rep(i,l,r+1) a[i]=min(a[i],x); else{
            mst(p,0); rep(i,l,r+1) p[a[i]]++;
            int ans(0); rep(i,1,n+1){
                int at=ans; ans+=p[i];
                if(at<ans&&ans>=x){ pf("%d\n",i); break; }
            }
        }
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

java

登录后参与评论

0 条评论

热度