A. 跑步
分析
因为权值的变化只是加一减一
所以 (dp) 值的变化也只是加一减一
设第 (i) 行修改的区间为 ([li,ri])
那么对于任意 (i<j) 有 (l_i leq l_j,r_i leq r_j)
直接差分，树状数组维护，然后单调指针扫一遍
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e3+5;
int n,a[maxn][maxn],tr[maxn][maxn],f[maxn][maxn];
long long ans=0;
int lb(rg int xx){
return xx&-xx;
}
void ad(rg int i,rg int j,rg int val){
for(rg int o=j;o<=n;o+=lb(o)){
tr[i][o]+=val;
}
}
int cx(rg int i,rg int j){
rg int nans=0;
for(rg int o=j;o>0;o-=lb(o)){
nans+=tr[i][o];
}
return nans;
}
void solve(rg int nx,rg int ny,rg int val){
rg int l=ny,r=ny;
for(int i=nx;i<=n;++i){
while(cx(i,l)==std::max(cx(i-1,l),cx(i,l-1))+a[i][l] && l<=n) l++;
ad(i,l,val),ad(i,r+1,-val);
while(cx(i,r+1)!=std::max(cx(i-1,r+1),cx(i,r))+a[i][r+1] && r<n){
r++;
ad(i,r,val),ad(i,r+1,-val);
}
if(l<=r) ans+=val*(r-l+1);
}
printf("%lld
",ans);
}
int main(){
n=read();
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
a[i][j]=read();
}
}
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
f[i][j]=std::max(f[i-1][j],f[i][j-1])+a[i][j];
}
}
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
ans+=f[i][j];
ad(i,j,f[i][j]-f[i][j-1]);
}
}
printf("%lld
",ans);
rg char ch;
rg int aa,bb;
for(rg int i=1;i<=n;i++){
scanf(" %c",&ch);
aa=read(),bb=read();
if(ch=='U') a[aa][bb]++;
else a[aa][bb]--;
solve(aa,bb,ch=='U'?1:-1);
}
return 0;
}
B. 算术
分析
对于一个质数 (p)，有 (x^{p−1} equiv 1(mod p))
而如果 (p) 可以表示成 (ak+1) 那么就是说 (x^{ak} equiv 1(mod p))
那么就有 (n^a equiv 1(mod p))
多枚举几个 (a) 进行判断就行了，正确率很高
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int t,k,n,tag;
char s[maxn];
bool jud(rg long long ds,rg int zs,rg int mod){
rg long long nans=1;
while(zs){
if(zs&1) nans=nans*ds%mod;
ds=ds*ds%mod;
zs>>=1;
}
return nans<=1;
}
bool judprime(rg int now){
if(now==2) return 1;
for(rg int i=2;i*i<=now;i++){
if(now%i==0) return 0;
}
return 1;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%s%d",s+1,&k);
n=strlen(s+1);
tag=1;
for(rg int o=1;o<=20;o++){
rg int tmp=o*k+1;
rg long long sum=0;
if(judprime(tmp)){
for(rg int i=1;i<=n;i++){
sum=sum*10+(s[i]-'0');
sum%=tmp;
}
if(!jud(sum,o,tmp)){
tag=0;
break;
}
}
}
if(tag) printf("Y
");
else printf("N
");
}
return 0;
}
C. 求和
分析
答案一定会出现在满足 (j in [i−k,i+k],a_j leq a_i) 的 (i) 上
发现权值相同时不好处理
所以将条件改为左边小于等于，右边小于，这与原来的条件是等价的
这样在权值相等的时候找坐标最大的就行了
用线段树会被卡常，所以要用 (zkw)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int n,k,q,op,a[maxn],ans,tr[maxn<<2],pos[maxn<<2],bit;
int cmp(rg int aa,rg int bb){
return a[aa]>a[bb]?aa:(a[aa]==a[bb]?std::max(aa,bb):bb);
}
void build(){
for(bit=1;bit<=n;bit<<=1);
for(rg int i=1;i<=n;i++) pos[i+bit]=i;
for(rg int i=bit-1;i>0;i--) pos[i]=cmp(pos[i<<1],pos[i<<1|1]);
}
void xg(rg int wz,rg int val){
for(tr[wz+=bit]=val,wz>>=1;wz>0;wz>>=1) tr[wz]=std::max(tr[wz<<1],tr[wz<<1|1]);
}
int cx(rg int l,rg int r){
rg int nans=0;
for(l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){
if(~l&1) nans=cmp(nans,pos[l^1]);
if(r&1) nans=cmp(nans,pos[r^1]);
}
return nans;
}
void updat(rg int wz){
for(wz+=bit,wz>>=1;wz>0;wz>>=1) pos[wz]=cmp(pos[wz<<1],pos[wz<<1|1]);
}
void judmax(rg int wz){
if(!wz) return;
rg int le=(wz==1)?0:cx(std::max(1,wz-k),wz-1);
rg int ri=(wz==n)?0:cx(wz+1,std::min(wz+k,n));
if(a[wz]>=a[le] && a[wz]>a[ri]) xg(wz,a[wz]+std::max(a[le],a[ri]));
else if(tr[wz+bit]) xg(wz,0);
}
int latans;
int solve(rg int wz){
rg int le=(wz==1)?0:cx(std::max(1,wz-k),wz-1);
rg int ri=(wz==n)?0:cx(wz+1,std::min(wz+k,n));
judmax(wz),judmax(le),judmax(ri);
return tr[1];
}
int main(){
n=read(),k=read(),q=read(),op=read();
for(rg int i=1;i<=n;i++) a[i]=read();
build();
rg int aa,bb;
for(rg int i=1;i<=n;i++) judmax(i);
printf("%d
",latans=tr[1]);
for(rg int i=1;i<=q;i++){
aa=read(),bb=read();
if(op) aa^=latans,bb^=latans;
a[aa]=bb,updat(aa);
printf("%d
",latans=solve(aa));
}
return 0;
}