A
模拟即可。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 50050
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,m,t[N];
int vis[N];
IL void work()
{
n=read(),m=read(),memset(t+1,-1,n<<2),memset(vis+1,0,m<<2);
for(reg int i=1,x,c=n;i<=m;++i)
{
x=read()-n;
if(!vis[x])
{
vis[x]=1;
if(c)t[c--]=i;
}
}
for(reg int i=1;i<=n;++i)printf("%d ",t[i]); puts("");
}
main()
{
for(reg int t=read();t--;work());
}
B
如果存在 \(1\) 且不全是 \(1\) 则无解，否则每次选两个不同的数操作，显然可以在 \(O(nlogV)\) 次内完成目标。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 110
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,x[N];
bool flag1,flag2;
int s[1001000][2],top;
IL void print()
{
printf("%d\n",top);
for(reg int i=1;i<=top;++i)printf("%d %d\n",s[i][0],s[i][1]);
}
IL void work()
{
n=read(),flag1=1,flag2=0,top=0;
for(reg int i=1;i<=n;++i)x[i]=read(),flag2|=x[i]==1;
for(reg int i=2;i<=n;++i)flag1&=x[i]==x[i-1];
if(flag1)return puts("0"),void();
if(flag2)return puts("-1"),void();
while(1)
{
flag1=1;
for(reg int i=2;i<=n;++i)flag1&=x[i]==x[i-1];
if(flag1)return print();
for(reg int i=1,j;i<=n;++i)for(j=1;j<=n;++j)if(x[i]>x[j])
x[i]=(x[i]-1)/x[j]+1,s[++top][0]=i,s[top][1]=j;
}
}
main()
{
for(reg int t=read();t--;work());
}
C
这题赛时花了我 \(\texttt{30min}\)，溜大了。
钦定正序较大，从 a 到 z 依次枚举字符，找到第一个出现次数为奇数次的字符。
对于接下来出现的字符的种数，分别有一种贪心。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 100100
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
char s[N],pre[N],suf[N];
int n,c[30],m1,m2,pos,cnt;
bool flag;
IL void print()
{
for(reg int i=1;i<=m1;++i)putchar(pre[i]);
for(reg int i=m2;i;--i)putchar(suf[i]);
puts("");
}
IL void work()
{
scanf("%s",s+1),n=strlen(s+1);
memset(c,0,sizeof(c));
for(reg int i=1;i<=n;++i)++c[s[i]-'a'];
m1=m2=0; pos=26;
for(reg int i=0;i<26;++i)if(c[i]&1){pos=i; break;}
for(reg int i=0,j;i<=pos;++i)for(j=1;j<=c[i]/2;++j)pre[++m1]=suf[++m2]=i+'a';
if(pos==26)return print();
cnt=0;
for(reg int i=pos+1;i<26;++i)cnt+=!!c[i];
if(!cnt)
{
pre[++m1]=pos+'a';
}else if(cnt==1)
{
for(reg int i=pos+1,j;i<26;++i)if(c[i])
{
for(j=1;j<=(c[i]+1)/2;++j)pre[++m1]=i+'a';
for(j=1;j<=c[i]/2;++j)suf[++m2]=i+'a';
}
pre[++m1]=pos+'a';
}else
{
suf[++m2]=pos+'a';
for(reg int i=pos+1,j;i<26;++i)if(c[i])
{
for(j=c[i];j--;)pre[++m1]=i+'a';
}
}
print();
}
main()
{
for(reg int t=read();t--;work());
}
D
首先有个简单 dp，设 \(f(i,j)\) 表示考虑了前 \(i\) 个任务，没有执行最后一个任务的机子执行的是 \(j\)。
转移是容易的，这个 \(O(n^2)\) 的做法可以通过 easy version。
显然地，线段树可以优化这一 dp 过程，复杂度降至 \(O(nlogn)\)。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 300300
#define int long long
#define oo (1ll<<60)
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,k,a[N],v1[N],v2[N];
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l[o]+r[o]>>1)
int l[N<<2],r[N<<2],mn[N<<2],tag[N<<2];
IL void build(reg int o,reg int L,reg int R)
{
l[o]=L,r[o]=R,tag[o]=0,mn[o]=!L?0:oo;
if(L<R)build(ls,L,mid),build(rs,mid+1,R);
}
IL void pushup(reg int o){mn[o]=std::min(mn[ls],mn[rs]);}
IL void upd(reg int o,reg int k){mn[o]+=k,tag[o]+=k;}
IL void pushdown(reg int o){if(tag[o])upd(ls,tag[o]),upd(rs,tag[o]),tag[o]=0;}
void insert(reg int o,reg int p,reg int k)
{
if(l[o]==r[o])mn[o]=std::min(mn[o],k);
else pushdown(o),insert(mid>=p?ls:rs,p,k),pushup(o);
}
int query(reg int o,reg int p)
{
if(l[o]==r[o])return mn[o];
return pushdown(o),query(mid>=p?ls:rs,p);
}
IL void work()
{
n=read(),k=read();
for(reg int i=1;i<=n;++i)a[i]=read();
for(reg int i=1;i<=k;++i)v1[i]=read();
for(reg int i=1;i<=k;++i)v2[i]=read();
build(1,0,k);
for(reg int i=1,x,k;i<=n;++i)
{
x=a[i],k=std::min(mn[1]+v1[x],query(1,x)+v2[x]);
upd(1,x==a[i-1]?v2[x]:v1[x]),insert(1,a[i-1],k);
}
printf("%lld\n",mn[1]);
}
main()
{
for(reg int t=read();t--;work());
}
E
考虑一个满足条件的联通块有什么性质——他的四个边界都是“单峰”的（左边界，右边界，上边界，下边界）。
枚举左右边界的极值，限制形如在每一行，一定要包含某个区间，且一定要将两个联通块连起来。可以直接扫几遍，计算出每一行的左端点最大值，右端点最小值。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 55
#define oo (1<<30)
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,m,up,down,L[N],R[N],l[N],r[N],ans;
bool turn;
char s[N][N],t[N][N];
int pre[N][N];
IL void cmin(reg int &x,reg int y){x>y?x=y:0;}
IL void cmax(reg int &x,reg int y){x<y?x=y:0;}
IL void work()
{
n=read(),m=read(),ans=oo;
for(reg int i=1;i<=n;++i)scanf("%s",s[i]+1);
if(n>m)
{
turn=1;
for(reg int i=1,j;i<=n;++i)for(j=1;j<=m;++j)t[j][i]=s[i][j];
std::swap(n,m);
for(reg int i=1,j;i<=n;++i)for(j=1;j<=m;++j)s[i][j]=t[i][j];
}else turn=0;
for(reg int i=1,j;i<=n;++i)for(j=1;j<=m;++j)if(s[i][j]=='#')down=i;
for(reg int i=n,j;i;--i)for(j=1;j<=m;++j)if(s[i][j]=='#')up=i;
for(reg int i=up,j;i<=down;++i)
{
L[i]=m,R[i]=1;
for(j=1;j<=m;++j)if(s[i][j]=='#')R[i]=j;
for(j=m;j;--j)if(s[i][j]=='#')L[i]=j;
}
for(reg int i=up,j;i<=down;++i)for(j=1;j<=m;++j)pre[i][j]=pre[i][j-1]+(s[i][j]=='.');
for(reg int i=up,j,k,o,res;i<=down;++i)for(j=up;j<=down;++j)
{
for(k=up-1;k<=down+1;++k)l[k]=m,r[k]=1;
for(k=up;k<=i;++k)cmin(l[k],l[k-1]),cmin(l[k],L[k]);
for(k=down;k>=i;--k)cmin(l[k],l[k+1]),cmin(l[k],L[k]);
for(k=up;k<=j;++k)cmax(r[k],r[k-1]),cmax(r[k],R[k]);
for(k=down;k>=j;--k)cmax(r[k],r[k+1]),cmax(r[k],R[k]);
for(k=up+1;k<=down;++k)cmax(r[k],l[k-1]);
for(k=down-1;k>=up;--k)cmax(r[k],l[k+1]),cmin(l[k],r[k]);
res=0;
for(k=up;k<=down;++k)res+=pre[k][r[k]]-pre[k][l[k]-1];
if(res<ans)
{
ans=res;
for(k=1;k<=n;++k)for(o=1;o<=m;++o)t[k][o]='.';
for(k=up;k<=down;++k)for(o=l[k];o<=r[k];++o)t[k][o]='#';
}
}
if(turn)
{
for(reg int i=1,j;i<=n;++i)for(j=1;j<=m;++j)s[j][i]=t[i][j];
std::swap(n,m);
for(reg int i=1,j;i<=n;++i)for(j=1;j<=m;++j)t[i][j]=s[i][j];
}
for(reg int i=1,j;i<=n;++i,puts(""))for(j=1;j<=m;++j)putchar(t[i][j]);
puts("");
}
main()
{
for(reg int t=read();t--;work());
}
F
将原数组排序。
枚举有多少个数执行了两种操作，容易发现并证明这些数肯定是最大的那些。
考虑每个数只能选其中一种操作。
枚举有多少个 \(a_i\ge b\) 执行了 \(a_i-b\) 操作，这些 \(a_i\) 肯定是最小的那些。
再观察 \(a_i<b\)，执行 \(a_i-b\) 操作的肯定是最大的那些。
再在剩下的数中，降序使用折半。
时间复杂度 \(O(n^2)\)。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define int long long
#define N 5050
#define oo (1ll<<60)
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,m,b,k1,k2,x[N],s1[N],s2[N],ans,sum;
IL int max(reg int x,reg int y){return x>y?x:y;}
IL int min(reg int x,reg int y){return x<y?x:y;}
IL int Ceil(reg int x){return x+1>>1;}
IL void work()
{
n=read(),b=read(),k1=read(),k2=read(),sum=0;
for(reg int i=1;i<=n;++i)x[i]=read(),sum+=x[i];
std::sort(x+1,x+1+n),ans=-oo;
for(reg int c=0,i,l,r,res,w,d;;++c)
{
m=n-c;
for(res=0,i=n;i>m;--i)res+=x[i]-max(0,Ceil(x[i])-b);
for(i=1;i<=m;++i)s1[i]=s1[i-1]+x[i]-max(0,x[i]-b);
for(i=1;i<=m;++i)s2[i]=s2[i-1]+x[i]-Ceil(x[i]);
// for(i=1;i<=m;++i)if(x[i]>=b)break;
for(i=m+1;i;--i)
{
w=res,l=i,r=min(i+k2-1,m),w+=s1[r]-s1[l-1];
l=r+1,r=min(l+k1-1,m),w+=s2[r]-s2[l-1],d=r-l+1;
r=i-1,l=max(1,r-(k1-d)+1),w+=s2[r]-s2[l-1];
ans=std::max(ans,w);
}
if(!k1||!k2)break;
--k1,--k2;
}
printf("%lld\n",sum-ans);
}
main()
{
for(reg int t=read();t--;work());
}
G
弱智计数题，认为每个人得到的每一票的并不是相同的票，最后除以重排方案数。
则我们可以把同一组放在一起考虑，算出人数和所获票数。
接下来就是一个简单背包，时间复杂度 \(O(n^3)\)。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define mod 998244353
#define N 220
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL int Mul(reg int x,reg int y){reg long long r=1ll*x*y; return r<mod?r:r%mod;}
int fac[N],ifac[N],inv[N];
IL void init(reg int n)
{
inv[1]=fac[0]=ifac[0]=1;
for(reg int i=2;i<=n;++i)inv[i]=Mul(mod-mod/i,inv[mod%i]);
for(reg int i=1;i<=n;++i)fac[i]=Mul(fac[i-1],i),ifac[i]=Mul(ifac[i-1],inv[i]);
}
IL int C(reg int n,reg int m){return Mul(fac[n],Mul(ifac[m],ifac[n-m]));}
IL int A(reg int n,reg int m){return Mul(fac[n],ifac[n-m]);}
int n,x[N],y[N],c[N],t[N],f[N][N],ans;
main()
{
n=read(),init(n);
for(reg int i=1;i<=n;++i)c[i]=read();
for(reg int i=1;i<=n;++i)t[i]=read(),++x[t[i]],y[t[i]]+=c[i];
f[0][0]=1;
for(reg int i=1,j,k,l,sx=0,sy=0,w;i<=n;++i)
{
for(j=0;j<=sx;++j)if(w=f[i-1][j])for(k=0;k<=sx-j&&k<=y[i];++k)for(l=0;l<=x[i]&&l+j<=sy;++l)
Pls(f[i][j+k+l],Mul(w,Mul(Mul(C(x[i],l),A(sy-j,l)),Mul(C(sx-j,k),A(y[i],k)))));
sx+=x[i],sy+=y[i]; // people, votes
}
ans=f[n][n];
for(reg int i=1;i<=n;++i)ans=Mul(ans,ifac[c[i]]);
printf("%d\n",ans);
}
H
赛时没过，咕咕咕。
标签：ch,int,笔记,CF1799,read,解题,IL,reg,define From： https://www.cnblogs.com/Nesraychan/p/17169509.html