2020年河南省CCPC题解
Problem A. 班委竞选
设 ax 为第 x 类班干部最大票数。从小到大枚举学号i，若新x>ax则更新ax并且记录i为ansx的答案
void solve(){
int n=read(),m=read();
for(int i=1;i<=n;i++){
int x=read(),y=read();
if(a[x]<y){
a[x]=y;
ans[x]=i;
}
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<" ";
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem B. 广告投放
本题的朴素dp思路很好想，但是空间上是O(nm)，时间上也是O(nm)。
想到[n/i]的取值只有O(√n)种，然后就预处理出取值可能(赛后知道 这是数论分块)，之后的转移方程很好想
void solve(){
int n=read(),m=read();
for(int i=1;i<=n;i++){
p[i]=read();
}
for(int i=1;i<=n;i++){
d[i]=read();
}
int cnt=0;
for(int i=1;i<=m;i++){
if(v[m/i]==0) mayp[++cnt]=m/i,v[m/i]=1;
}
mayp[0]=0;
sort(mayp,mayp+cnt+1);
for(int i=1;i<=n;i++){
for(int j=0;j<=cnt;j++){
dp[mayp[j]/d[i]]=max(dp[mayp[j]]+p[i]*mayp[j],dp[mayp[j]/d[i]]);
}
}
int ans=0;
for(int i=0;i<=cnt;i++){
ans=max(ans,dp[mayp[i]]);
}
cout<<ans<<endl;
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem C. 我得重新集结部队
纯模拟 但是很简单
struct node{
int p,x,y,h,r,atk,li;
}a[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
a[i].p=read();
if(a[i].p==1){
a[i].x=read();
a[i].y=read();
a[i].h=read();
a[i].li=1;
}else {
a[i].x=read();
a[i].y=read();
a[i].atk=read();
a[i].r=read();
a[i].li=1;
int rx=-1,ry=-1,ans=INF;
for(int j=1;j<i;j++){
if(a[j].p==1&&a[j].li==1){
int temp=(a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y);
if(temp<ans){
ans=temp;
rx=a[j].x;
ry=a[j].y;
}
}
}
int out=0;
for(int j=1;j<i;j++){
if(a[j].p==1&&a[j].li==1&&(rx-a[j].x)*(rx-a[j].x)+(ry-a[j].y)*(ry-a[j].y)<=a[i].r*a[i].r){
a[j].h-=3*a[i].atk;
if(a[j].h<=0)a[j].li=0;
else out=1;
}
}
if(out==1)a[i].li=0;
}
}
for(int i=1;i<=n;i++){
puts(a[i].li==1?"Yes":"No");
}
//puts(ans>0?"YES":"NO");
}
Problem E. 发通知
我认为还是个小模拟，题目本身不难，但是在区间里容易想偏（至少我是这样的额）
struct node{
int poi,op,w;
friend bool operator<(const node&a,const node&b){
return a.poi<b.poi;
}
}a[N];
void solve(){
int n=read(),k=read();
int cnt=0;
for(int i=1;i<=n;i++){
int x=read(),y=read(),z=read();
a[cnt++]={x,0,z};
a[cnt++]={y+1,1,z};
}
sort(a,a+cnt);
int num=0,sum=0,ans=-1;
for(int i=0;i<cnt;i++){
int poi=a[i].poi,w=a[i].w,op=a[i].op;
if(!op){
num++;
sum^=w;
if(num>=k&&a[i+1].poi!=poi){
ans=max(ans,sum);
}
}else{
num--;
sum^=w;
if(num>=k&&a[i+1].poi!=poi){
ans=max(ans,sum);
}
}
}
if(ans>=0)cout<<ans<<endl;
else cout<<-1<<endl;
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem I. 太阳轰炸
本题思路很清楚 将题目的模型最后转化为求一个O(n)长度的组合数的和
又因为要求逆元 自然的想到预处理阶乘和阶乘的逆元
int fac[N],inv[N];
inline int combination(int n,int k){
return fac[n]*inv[k]%mod*inv[n-k]%mod;
}
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
void solve(){
int n=read(),r1=read(),r2=read(),r=read(),a=read(),h=read();
int k=(h-1)/a+1;
if(k>n){
cout<<0<<endl;
return;
}
if(r2<=(r1+r)){
cout<<1<<endl;
return ;
}
fac[0]=1;
for(int i=1;i<=n+1;i++) fac[i]=fac[i-1]*i%mod;
inv[n+1]=qmi(fac[n+1],mod-2,mod);
for(int i=n;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
int rn=qmi(r2*r2%mod,mod-2,mod);
int p=(r1+r)*(r1+r)%mod*rn%mod;
int q=(r2*r2%mod-(r1+r)*(r1+r)%mod+mod)%mod*rn%mod;
int pk=qmi(p,k,mod);
int qnk=qmi(q,n-k,mod);
LL res=0;
for(int i=k;i<=n;i++)
{
res=res+combination(n,i)*pk%mod*qnk%mod;
res%=mod;
pk=(LL)pk*p%mod;
qnk=(LL)qnk*qmi(q,mod-2,mod)%mod;
}
printf("%lld\n",res);
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
}
Problem J. 二进制与、平方和
题目一眼线段树 但是阅历太浅 根本想不到怎么做
modify的时候如果与上目标值对结果无影响就return 因为只有原值1&目标值0的时候才会有影响 显然每个位置最多变化loga 乍一看时间复杂度是O(nlognloga) 但是实际上O(n(logn+loga))
网上的代码都千遍一律 线段树里有一个25的数组 时间效率低 codeforces上至少要1900ms 这份只要400ms
int n, q, a[N];
struct Info{
int sum, orsum;
}seg[N << 2];
Info operator + (const Info &a, const Info &b){
Info c;
c.orsum = a.orsum | b.orsum;
c.sum = a.sum + b.sum;
return c;
}
void up(int id){
seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
void build(int id, int l, int r){
if(l == r){
seg[id].orsum = a[l] % mod;
seg[id].sum = (a[l] * a[l]) % mod;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
up(id);
}
void modify(int id, int l, int r, int ql, int qr, int val){
if((seg[id].orsum & val) == seg[id].orsum) return;
if(l == r){
seg[id].orsum = seg[id].orsum & val;
seg[id].sum = (seg[id].orsum * seg[id].orsum) % mod;
return;
}
int mid = (l + r) >> 1;
if(qr <= mid){
modify(id << 1, l, mid, ql, qr, val);
}else if(ql> mid){
modify(id << 1 | 1, mid + 1, r, ql, qr, val);
}else{
modify(id << 1, l, mid, ql, mid, val);
modify(id << 1 | 1, mid + 1, r, mid + 1, qr, val);
}
up(id);
}
int query(int id, int l, int r, int ql, int qr){
if(l == ql && r == qr){
return seg[id].sum;
}
int mid = (l + r) >> 1;
if(qr <= mid){
return query(id << 1, l, mid, ql, qr);
}else if(ql > mid){
return query(id << 1 | 1, mid + 1, r, ql, qr);
}else{
return query(id << 1, l, mid, ql, mid) + query(id << 1 | 1, mid + 1, r, mid + 1, qr);
}
}
signed main(){
cin >> n;
for(int i = 1; i <= n ; i ++) cin >> a[i];
build(1, 1, n);
cin >> q;
while(q --){
int ty, l, r;
cin >> ty >> l >> r;
if(ty == 1){
int x;
cin >> x;
modify(1, 1, n, l, r, x);
}else{
cout << query(1, 1, n, l, r)% mod << endl;
}
}
}
标签：int,题解,CCPC,read,2020,ans,Problem,YES,mod From： https://www.cnblogs.com/edgrass/p/17216062.html