Wannafly Winter Camp 2020-Day1

第一场比赛还算比较顺利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. 密码学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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. 染色图

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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) System.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. 期望逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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. 乘法

生 涯 之 耻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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可以过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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; }
}
}
}
}