传送门
GGG题手速慢了没有在比赛的时候码出来233,FFF题居然没想出来？
五道题滚粗。
先谈谈其他几道题。
A题
传送门 不小心看错题
直接看奇偶性构造答案。
如果是奇数就用一个3和几个2，不然就全部用2.
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=105;
int n,a[N],f[N];
int main(){
n=read(),f[0]=1;
for(ri i=1;i<=n;++i){
int x=read();
if(x&1)cout<<1+(x-3)/2<<'\n';
else cout<<x/2<<'\n';
}
return 0;
}
B题
传送门 明显送分
我们直接将所有字符串排序，看有没有所有字符都是一样的就行了。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=105;
char s[10005];
int t;
int main(){
t=read();
while(t--){
scanf("%s",s+1);
int n=strlen(s+1);
sort(s+1,s+n+1);
bool f=0;
for(int i=1;i<n;++i)if(s[i]!=s[i+1]){f=1;break;}
if(!f){puts("-1");continue;}
for(ri i=1;i<=n;++i)cout<<s[i];
puts("");
}
return 0;
}
C题
传送门 明显送分
按照题意模拟。
由于题目保证有合法方案，因此我们先保证aia_iai最小，如果aia_iai不合法就保证an−i+1a_{n-i+1}an−i+1最大。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=2e5+5;
int n;
ll a[N],b[N];
int main(){
n=read();
for(ri i=1;i<=n/2;++i)b[i]=read();
for(ri i=1;i<=n/2;++i){
a[i]=a[i-1],a[n-i+1]=b[i]-a[i];
if(a[n-i+1]>a[n-i+2]&&i!=1)a[n-i+1]=a[n-i+2],a[i]=b[i]-a[n-i+1];
}
for(ri i=1;i<=n;++i)cout<<a[i]<<' ';
return 0;
}
D题
传送门 明显送分
题目要说的就是相邻两点奇偶性不同。
因此可以假设一号点为奇，先二分图染色看是否合法。
如果对于某个yyy个点的子图这时候编号为奇数的点有xxx个，那么这个子图的贡献就是2x+2y−x2^x+2^{y-x}2x+2y−x，最后乘起来就行了。
代码：
#include<bits/stdc++.h>
#define ri long long
#define int long long
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=3e5+5,mod=998244353;
int n,t,m,col[N],cnt=0,tot=0;
vector<int>e[N];
inline bool dfs(int p,int val){
++cnt,col[p]=val;
if(!val)++tot;
for(ri i=0;i<e[p].size();++i){
int v=e[p][i];
if(~col[v]){
if(col[v]==col[p])return false;
continue;
}
if(!dfs(v,val^1))return false;
}
return true;
}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=(ll)a*a%mod)if(p&1)ret=(ll)ret*a%mod;return ret;}
signed main(){
for(ri tt=read();tt;--tt){
n=read(),m=read();
for(ri i=1;i<=n;++i)e[i].clear(),col[i]=-1;
for(ri i=1,u,v;i<=m;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
ll ans=1;
bool f=1;
for(ri i=1;i<=n;++i){
if(col[i]==-1){
cnt=0,tot=0;
if(!dfs(i,0)){
f=false;
break;
}
ans=(ll)ans*(ksm(2,tot)+ksm(2,cnt-tot))%mod;
}
}
if(!f){puts("0");continue;}
cout<<ans<<'\n';
}
return 0;
}
E题
传送门 有点烦人
把一个数iii在a,ba,ba,b数列中的下标ai,bia_i,b_iai,bi看成坐标，然后相当于就是一个二维数点问题了。
直接上cdqcdqcdq分治即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=2e5+5,M=2e5+5,K=2e5+5;
struct Pot{int x,y,z,t,id,f;}q[N<<3],tmp[N<<3];
struct Node{int x,y;}pos[N];
int n,s,k,m,m_,bit[M],ans[K],a[N],b[N];
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
inline int lowbit(int x){return x&-x;}
inline void update(int x,int v){for(int i=x;i<=n;i+=lowbit(i))bit[i]+=v;}
inline int query(int x){int ret=0;for(int i=x;i;i-=lowbit(i))ret+=bit[i];return ret;}
void solve(int l,int r){
if(l==r)return;
int mid=l+r>>1,pos1=l,pos2=mid+1;
for(ri i=l;i<=r;++i){
if(q[i].t<=mid&&!q[i].f)update(q[i].y,q[i].z);
if(q[i].t>mid&&q[i].f)ans[q[i].id]+=q[i].z*query(q[i].y);
}
for(ri i=l;i<=r;++i)if(q[i].t<=mid&&!q[i].f)update(q[i].y,-q[i].z);
for(ri i=l;i<=r;++i)
if(q[i].t<=mid)tmp[pos1++]=q[i];
else tmp[pos2++]=q[i];
for(ri i=l;i<=r;++i)q[i]=tmp[i];
solve(l,mid),solve(mid+1,r);
}
inline bool cmp(Pot a,Pot b){return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.f<b.f);}
int main(){
n=read(),m=read(),k=0,m_=0;
for(ri i=1;i<=n;++i)pos[a[i]=read()].x=i;
for(ri i=1;i<=n;++i)pos[b[i]=read()].y=i;
for(ri i=1;i<=n;++i)q[++k]=(Pot){pos[i].x,pos[i].y,1,k,m_,0};
for(ri i=1,op,x1,x2,y1,y2;i<=m;++i){
op=read();
if(op==1){
++m_,x1=read()-1,x2=read(),y1=read()-1,y2=read();
q[++k]=(Pot){x1,y1,1,k,m_,1};
q[++k]=(Pot){x1,y2,-1,k,m_,1};
q[++k]=(Pot){x2,y1,-1,k,m_,1};
q[++k]=(Pot){x2,y2,1,k,m_,1};
}
else{
int x=read(),y=read();
#define b1 pos[b[x]]
#define b2 pos[b[y]]
q[++k]=(Pot){b1.x,b1.y,-1,k,m_,0};
q[++k]=(Pot){b2.x,b2.y,-1,k,m_,0};
swap(b[x],b[y]),b1.y=x,b2.y=y;
q[++k]=(Pot){b1.x,b1.y,1,k,m_,0};
q[++k]=(Pot){b2.x,b2.y,1,k,m_,0};
}
}
sort(q+1,q+k+1,cmp),solve(1,k);
for(ri i=1;i<=m_;++i)cout<<ans[i],puts("");
}
F题
传送门 送分没拿
考虑dpdpdp。
fi,jf_{i,j}fi,j表示当前在第iii个位置，第iii个位置放jjj的合法方案数。
显然可以从上一个位置的递推过来，然后判断是否需要扣去这连续kkk个都相同的方案数。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e5+5,K=105,mod=998244353;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,k,len,a[N],f[N][105],g[N],ans[N],cnt[N];
int main(){
freopen("lx.in","r",stdin);
n=read(),k=read(),len=read();
for(ri i=1;i<=n;++i)a[i]=read();
if(len<2)puts("0"),exit(0);
g[0]=ans[0]=1;
for(ri i=1;i<=n;++i){
for(ri j=1;j<=k;++j){
if(a[i]==j||a[i]==-1){
f[i][j]=(ans[i-1]-g[j]+mod)%mod;
++cnt[j];
if(cnt[j]>=len-1)g[j]=(ans[i-len+1]-f[i-len+1][j]+mod)%mod;
}
else cnt[j]=g[j]=0;
ans[i]=(ans[i]+f[i][j])%mod;
}
}
cout<<ans[n];
return 0;
}
G题
传送门 有点可惜
比赛的时候没时间做了233。
我们考虑如同scoi2018pipiscoi2018pipiscoi2018pipi酱的日常那种做法，把绝对值拆开。
即拆开曼哈顿距离乱搞。
相当于维护∑i=1k(+ai/−ai)\sum_{i=1}^k(+a_i/-a_i)∑i=1k(+ai/−ai)的区间最大值。
什么意思呢？
对于一个点ppp，我们把它的各维度的不同组合方式用2k2^k2k个状态存起来。
准确地说，就是每个二进制位表示这个点在这个维度上是正的还是负的贡献（不妨设000为负111为正），记做statep,0...2k−1state_{p,0...2^k-1}statep,0...2k−1。
对于两个点(a1,a2,...,ak),(b1,b2,...,bk)(a_1,a_2,...,a_k),(b_1,b_2,...,b_k)(a1,a2,...,ak),(b1,b2,...,bk)，他们的距离是等于max{statea,i+stateb,2k−i−1}max\{state_{a,i}+state_{b,2^k-i-1}\}max{statea,i+stateb,2k−i−1}的。
于是维护区间的statestatestate变量的最大值然后加起来取maxmaxmax就可以了。
代码：
#include<bits/stdc++.h>
#define ri register int
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
using namespace std;
const int N=2e5+5;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,K,m,a[N][5],ans[32],up;
struct Node{int l,r,mx[32];}T[N<<2];
inline void pushup(int p){for(ri i=0;i<up;++i)T[p].mx[i]=max(T[lc].mx[i],T[rc].mx[i]);}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r){
for(ri i=0;i<up;++i){
int sum=0;
for(ri j=0;j<K;++j){
if((i>>j)&1)sum+=a[l][j];
else sum-=a[l][j];
}
T[p].mx[i]=sum;
}
return;
}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int k){
if(T[p].l==T[p].r){
for(ri i=0,sum=0;i<up;++i,sum=0){
for(ri j=0;j<K;++j){
if((i>>j)&1)sum+=a[k][j];
else sum-=a[k][j];
}
T[p].mx[i]=sum;
}
return;
}
if(k<=mid)update(lc,k);
else update(rc,k);
pushup(p);
}
inline void query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr){
for(ri i=0;i<up;++i)ans[i]=max(ans[i],T[p].mx[i]);
return;
}
if(qr<=mid)query(lc,ql,qr);
else if(ql>mid)query(rc,ql,qr);
else query(lc,ql,mid),query(rc,mid+1,qr);
}
int main(){
freopen("lx.in","r",stdin);
n=read(),K=read(),up=1<<K;
for(ri i=1;i<=n;++i)for(ri j=0;j<K;++j)a[i][j]=read();
build(1,1,n);
m=read();
while(m--){
int op=read();
if(op==1){
int x=read();
for(ri i=0;i<K;++i)a[x][i]=read();
update(1,x);
}
else{
int l=read(),r=read();
for(ri i=0;i<up;++i)ans[i]=-0x3f3f3f3f;
query(1,l,r);
int pri=0;
for(ri i=0;i<up;++i)pri=max(pri,ans[i]+ans[up-i-1]);
cout<<pri<<'\n';
}
}
return 0;
}