ISIJ 作业，所以来做了。
打星号的是我能力范围内想出来的。（[eJOI2018] 元素周期表很久以前见过，不清楚现在见到能不能做出来，所以不打星号）
[eJOI2017] 魔法（*）
每种字符出现次数相同，也就是每种字符的 (s_{r,c}-s_{l-1,c}) 相同。
注意到，若 (forall i,s_{l-1,i}-s_{l-1,0}=s_{r,i}-s_{r,0})，那么 ([l,r]) 满足要求，反之也成立。
那么就能随便做了。
时间复杂度看实现，我写的垃圾 (O(n|Sigma|log n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010,mod=1000000007;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,cnt,a[maxn],vis[128],pre[maxn][52],ans;
map<vector<int>,int> mp;
char s[maxn];
int main(){
n=read();
scanf("%s",s+1);
FOR(i,1,n){
if(!vis[s[i]]) vis[s[i]]=++cnt;
a[i]=vis[s[i]];
}
FOR(i,1,n) a[i]--;
FOR(i,1,n){
FOR(j,0,cnt-1) pre[i][j]=pre[i-1][j];
pre[i][a[i]]++;
}
FOR(i,0,n){
vector<int> v;
FOR(j,0,cnt-1) v.PB(pre[i][j]-pre[i][0]);
ans=(ans+mp[v])%mod;
mp[v]++;
}
printf("%d
",ans);
}
[eJOI2017] 六（*）
被 AGC 虐爆后，我养成了自闭就搜的习惯。
然后在这题用上了，就离谱（
首先我们只用考虑每次加的数包含哪些质因子。设这个质因子集合为 (S)。那么要求要求任意时刻，(S) 的出现次数不超过 (2)。
那么设 (f_T)，(T) 的第 (S) 位是 (0/1/2)，表示质因子集合为 (S) 的数已经有了多少个。
状态数 (O(3^{2^k}))，没救了。
但是这个状态是真的不满，直接搜搜记记。
实现优秀点就能过了。
顺便聊聊我从 2s+ 变成 0.2s 的过程：
- vector 改成两个 ll 压位。卡进 2s。
- 三进制改成四进制（要用 ull）。效果拔群。本地已经能 0.8s，然而洛谷太老爷了。
- 修改限制方式。本来我的写法是枚举加哪种数，然后判断限制，就有很多无用枚举。现在变成加数时就更新别的数的状态（能不能加）。这本来能过了，洛谷上 0.7s+，但后来时限改了。
- 求 (tot_s)（(s) 内的倍数的个数）用 (O(sqrt{n}k))。我也不知道当时怎么想的，改成 (O(sqrt{n}+2^kk)) 就洛谷上 0.3s+ 了，目前最优解。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> PII;
const int maxn=100010,mod=1000000007;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int k,tot[64],cnt[6];
ll n,p[6];
vector<int> v[64];
map<PII,int> mp;
inline int tbit(ull x,int p){
return (x>>(p<<1))&3;
}
int dfs(ull x,ull y){
if(mp.count(MP(x,y))) return mp[MP(x,y)];
int ans=1;
FOR(i,1,(1<<k)-1) if((i<32?tbit(x,i):tbit(y,i-32))<=1){
ll tmpx=x,tmpy=y;
bool flag=true;
FOR(jj,0,(int)v[i].size()-1){
int j=v[i][jj];
if(j<32){
if(tbit(x,j)<2) x+=1ull<<(j<<1);
}
else{
if(tbit(y,j-32)<2) y+=1ull<<((j-32)<<1);
}
}
if(flag) ans=(ans+1ll*dfs(x,y)*tot[i])%mod;
x=tmpx;y=tmpy;
}
return mp[MP(x,y)]=ans;
}
int main(){
n=read();
ll tmp=n;
for(int i=2;1ll*i*i<=n;i++) if(n%i==0){
p[k]=i;
while(n%i==0) n/=i,cnt[k]++;
k++;
}
if(n>1) p[k]=n,cnt[k++]=1;
n=tmp;
FOR(i,0,(1<<k)-1){
tot[i]=1;
FOR(j,0,k-1) if((i>>j)&1) tot[i]=1ll*tot[i]*cnt[j]%mod;
}
FOR(i,1,(1<<k)-1) FOR(j,1,(1<<k)-1) if(i&j) v[i].PB(j);
printf("%d
",(dfs(0,0)-1+mod)%mod);
}
[eJOI2017] 粒子（*）
每次操作时二分，判断此时跑到最右的 (x) 粒子是否在跑到最左的 (y) 粒子右边。模拟 (k) 次即可。
由于我相信 (O(nklog n)) 不能过，我们要接着优化。
其实就是求个半平面交的事。每次重构半平面交，然后把两边的上半部分分段加起来，在上面判断。
由于直线就那么几条，所以不用每次排序。
时间复杂度 (O(nlog n+nk))。
然后当我发现评测记录里一大堆 0.9s+ 的时候心态就崩了。
第二天我过来补代码，补着补着发现时限甚至变成了 2s，然后提交记录前几个 1.8s+。看起来就是暴力常数太大然后申请开大时限。
然后开始无 能 狂 怒。是真的无能，由于当时是那一天，发不了犇犇和帖子，连博客都不能发。
拿了个最优解不亏
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=50050,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
struct line{
int k,id1,id2;
ll b;
bool operator<(const line &l)const{
if(k!=l.k) return k<l.k;
return b>l.b;
}
}lx[maxn],ly[maxn],hx[maxn],hy[maxn],h[maxn*2];
int n,l,k,tx[maxn],vx[maxn],ty[maxn],vy[maxn],tpx,tpy,tot;
inline double interx(line l1,line l2){
return 1.0*(l1.b-l2.b)/(l2.k-l1.k);
}
line merge(line l1,line l2){
return (line){l1.k+l2.k,l1.id1,l2.id1,l1.b+l2.b};
}
int main(){
n=read();l=read();k=read();
FOR(i,1,n) tx[i]=read(),vx[i]=read(),lx[i]=(line){vx[i],i,0,-1ll*vx[i]*tx[i]};
FOR(i,1,n) ty[i]=read(),vy[i]=read(),ly[i]=(line){vy[i],i,0,-1ll*vy[i]*ty[i]};
sort(lx+1,lx+n+1);sort(ly+1,ly+n+1);
while(k--){
tpx=0;
FOR(i,1,n){
if(tpx && lx[i].k==hx[tpx].k) continue;
while(tpx>=2 && interx(lx[i],hx[tpx])<=interx(lx[i],hx[tpx-1])) tpx--;
hx[++tpx]=lx[i];
}
tpy=0;
FOR(i,1,n){
if(tpy && ly[i].k==hy[tpy].k) continue;
while(tpy>=2 && interx(ly[i],hy[tpy])<=interx(ly[i],hy[tpy-1])) tpy--;
hy[++tpy]=ly[i];
}
tot=0;
int j=1;
FOR(i,1,tpx){
double lft=i==1?-1e18:interx(hx[i],hx[i-1]),rig=i==tpx?1e18:interx(hx[i],hx[i+1]);
while(j<=tpy){
double L=j==1?-1e18:interx(hy[j],hy[j-1]),R=j==tpy?1e18:interx(hy[j],hy[j+1]);
if(L>rig) break;
if(R>=lft) h[++tot]=merge(hx[i],hy[j]);
if(R>rig) break;
j++;
}
}
int ans1=0,ans2=0;
FOR(i,1,tot){
double lft=i==1?-1e18:interx(h[i],h[i-1]),rig=i==tot?1e18:interx(h[i],h[i+1]);
double x=1.0*(l-h[i].b)/h[i].k;
if(x>=lft && x<=rig){
ans1=h[i].id1;
ans2=h[i].id2;
break;
}
}
printf("%d %d
",ans1,ans2);
FOR(i,1,n-1) if(lx[i].id1==ans1) swap(lx[i],lx[i+1]);
FOR(i,1,n-1) if(ly[i].id1==ans2) swap(ly[i],ly[i+1]);
n--;
}
}
[eJOI2017] 骆驼（*）
居然前几天模拟赛做过……
至少我写的很重工业。也幸好是模拟赛做过不然根本静不下心来写这个（
天哪要是我在现场怕不是要被这个题耗费一生然后白给了
这个范围提醒我们 (5 imes 5) 分成一块块。
然后瞎做。我用了类似下图的写法。
时间复杂度 (O(n^2))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1010,mod=998244353;
const int a1[5][5]={
{1,15,25,22,14},
{8,5,19,11,6},
{17,23,2,16,24},
{20,12,7,21,13},
{9,4,18,10,3}
};
const int a2[5][5]={
{1,11,8,20,12},
{16,5,23,15,6},
{9,19,2,10,25},
{22,14,7,21,13},
{17,4,24,18,3}
};
const int a3[5][5]={
{1,6,21,18,7},
{13,16,24,10,15},
{22,19,2,5,20},
{25,9,14,17,8},
{12,4,23,11,3}
}; // go out at 21
const int a4[5][5]={
{25,8,11,22,7},
{18,3,14,17,2},
{10,21,6,9,12},
{24,16,1,23,15},
{19,4,13,20,5}
};
const int a5[5][5]={
{24,13,16,23,1},
{4,21,10,5,18},
{15,7,2,14,8},
{25,12,17,22,11},
{3,20,9,6,19}
};
const int a6[5][5]={
{9,17,1,10,18},
{14,23,20,15,24},
{4,11,8,5,2},
{21,16,25,22,19},
{13,6,3,12,7}
};
const int a7[5][5]={
{9,2,21,10,1},
{19,5,13,16,6},
{22,25,8,3,24},
{12,15,20,11,14},
{18,4,23,17,7}
};
const int a8[5][5]={
{19,6,12,20,5},
{24,16,9,23,2},
{13,21,4,14,11},
{18,7,1,17,8},
{25,15,10,22,3}
};
const int a9[5][5]={
{25,10,7,22,11},
{18,15,4,1,16},
{8,21,12,9,6},
{24,2,17,23,3},
{19,14,5,20,13}
};
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,ans[maxn][maxn],cnt;
int main(){
n=read();
if(n%10==0){
FOR(i,0,4) FOR(j,0,4) ans[i][j]=a3[i][j]<=21?a3[i][j]:n*n-(25-a3[i][j]);
cnt=1;
FOR(i,0,n/5-1) if(i%2==0){
FOR(j,1,n/5-1) if(j!=n/5-1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a1[k][l];
cnt++;
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a2[k][l];
cnt++;
}
}
else{
ROF(j,n/5-1,1) if(j!=1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a1[k][4-l];
cnt++;
}
else if(i!=n/5-1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a2[k][4-l];
cnt++;
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a5[k][l];
cnt++;
}
}
ROF(i,n/5-1,1) FOR(j,0,0){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a4[k][l];
cnt++;
}
}
else{
FOR(i,0,4) FOR(j,0,4) ans[i][j]=a3[i][j]<=21?a3[i][j]:n*n-(25-a3[i][j]);
cnt=1;
FOR(i,0,n/5-3) if(i%2==0){
FOR(j,1,n/5-1) if(j!=n/5-1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a1[k][l];
cnt++;
}
else if(i!=n/5-3){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a2[k][l];
cnt++;
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a5[k][4-l];
cnt++;
}
}
else{
ROF(j,n/5-1,1) if(j!=1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a1[k][4-l];
cnt++;
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a2[k][4-l];
cnt++;
}
}
ROF(j,n/5-1,1) if((n/5-1-j)%2==0){
FOR(i,n/5-2,n/5-1) if(i==n/5-2){
if(j==n/5-1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a6[k][l];
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a7[4-l][4-k];
}
cnt++;
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a7[k][l];
cnt++;
}
}
else{
ROF(i,n/5-1,n/5-2) if(i==n/5-2){
if(j==1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a8[k][l];
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a7[4-k][l];
}
cnt++;
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a7[4-l][k];
cnt++;
}
}
ROF(i,n/5-1,1) FOR(j,0,0) if(i!=n/5-1){
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a4[k][l];
cnt++;
}
else{
FOR(k,0,4) FOR(l,0,4) ans[i*5+k][j*5+l]=cnt*25-4+a9[k][l];
cnt++;
}
}
FOR(i,0,n-1){
FOR(j,0,n-1) printf("%d ",ans[i][j]);
puts("");
}
}
[eJOI2017] 经验（*）
首先发现，对于每一条链，两个端点的 (w) 一定是一个链上最小值一个链上最大值。如果不是，那么找出最小值和最大值的位置，把外面的砍掉，不会变劣。
把题目变一下：选出一个链划分，若每条链的端点是 (u,v)，求 (|w_u-w_v|) 的和的最大值。
再变一下：选出一个链划分，若每条链的端点是 (u,v)，那么你可以选定这条链的价值是 (w_u-w_v) 还是 (w_v-w_u)，求链的价值的和的最大值。
那么设 (f_{u,0/1}) 表示 (u) 的子树内，(0) 表示 (u) 所在的链是浅的权值减去深的权值，(1) 反过来，的最大答案。
时间复杂度 (O(n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,el,head[maxn],to[maxn*2],nxt[maxn*2],w[maxn];
ll f[maxn][2];
inline void add(int u,int v){
to[++el]=v;nxt[el]=head[u];head[u]=el;
}
void dfs(int u,int F){
ll tot=0,mx0=-1e18,mx1=-1e18;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==F) continue;
dfs(v,u);
ll x=max(f[v][0]+w[v],f[v][1]-w[v]);
tot+=x;
mx0=max(mx0,f[v][0]-x);
mx1=max(mx1,f[v][1]-x);
}
f[u][0]=max(tot-w[u],tot+mx0);
f[u][1]=max(tot+w[u],tot+mx1);
}
int main(){
n=read();
FOR(i,1,n) w[i]=read();
FOR(i,1,n-1){
int u=read(),v=read();
add(u,v);add(v,u);
}
dfs(1,0);
printf("%lld
",max(f[1][0]+w[1],f[1][1]-w[1]));
}
[eJOI2017] 游戏
这题居然没想出来，大概可以退役了 /kk
显然每次取的都是最大的数。
问题变成每次加入一个数，然后把最大值删掉。
用一个指针记录最大值的位置。
注意到如果加入的数比目前的最大值大，那么它会立刻被删掉，直接处理。
否则，就暴力移指针。
指针只会往小了移，所以时间复杂度 (O(nk))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,q,a[maxn],cnt[maxn];
int main(){
n=read();q=read();
FOR(i,1,n) a[i]=read();
while(q--){
int k=read(),cur=0;
ll ans=0;
FOR(i,1,n) cnt[i]=0;
FOR(i,1,k-1) cnt[a[i]]++,cur=max(cur,a[i]);
FOR(i,1,n){
int x=cur;
if(k+i-1<=n){
if(a[i+k-1]>cur) x=a[i+k-1];
else cnt[a[i+k-1]]++,cnt[cur]--;
}
else cnt[cur]--;
while(cur && !cnt[cur]) cur--;
if(i%2==0) ans-=x;
else ans+=x;
}
printf("%lld
",ans);
}
}
[eJOI2018] 山（*）
两座被选定的山肯定不能相邻。
如果选定了保留哪些山，那么只有这些山两旁的山会被降低。
那么随便做了。
(f_{i,j,0/1/2}) 表示前 (i) 座山，选了 (j) 座留下，(0) 表示 (i) 和 (i-1) 都没留下，(1) 表示 (i-1) 留下了，(2) 表示 (i) 留下了。
时间复杂度 (O(n^2))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=5050,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,a[maxn],f[maxn][maxn/2][3];
int main(){
n=read();
FOR(i,1,n) a[i]=read();
FOR(i,0,n) FOR(j,0,(n+1)/2) f[i][j][0]=f[i][j][1]=f[i][j][2]=1e9;
f[0][0][0]=0;
FOR(i,1,n) FOR(j,0,(i+1)/2){
f[i][j][0]=min(f[i-1][j][0],f[i-1][j][1]);
f[i][j][1]=f[i-1][j][2];
if(j){
f[i][j][2]=f[i-1][j-1][0]+max(0,a[i-1]-a[i]+1)+max(0,a[i+1]-a[i]+1);
if(i>=2) f[i][j][2]=min(f[i-1][j-1][1]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1)+max(0,a[i+1]-a[i]+1),f[i][j][2]);
}
}
FOR(i,1,(n+1)/2) printf("%d ",min(min(f[n][i][0],f[n][i][1]),f[n][i][2]));
}
[eJOI2018] 护照
[eJOI2018] AB 串
声明：这题我没过。是因为洛谷计分系统的问题导致把我判成了 AC。
[eJOI2018] 元素周期表
还是很妙的。
把每行每列都抽象成点，一个点 ((x,y)) 就将第 (x) 行和第 (y) 行连边。
((x1,y1),(x1,y2),(x2,y1)) 都存在，那么第 (x2) 行和第 (y2) 行一定联通，此时也看做 ((x2,y2)) 存在。
所以会变成一堆联通块。答案就是联通块个数减一。
时间复杂度 (O(n+m+qmathrm{DSU}(n+m)))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=200020,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,m,q,fa[maxn*2],cnt;
int getfa(int x){
return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
int main(){
n=read();m=read();q=read();
cnt=n+m;
FOR(i,1,n+m) fa[i]=i;
while(q--){
int x=read(),y=read()+n;
x=getfa(x);y=getfa(y);
if(x!=y) fa[x]=y,cnt--;
}
printf("%d
",cnt-1);
}
[eJOI2018] 互素树
[eJOI2018] 循环排序
[eJOI2019] 异或橙子（*）
考虑询问 ([l,r]) 时，(i) 被异或了多少次。显然是 ((i-l+1)(r-i+1))。
当 (l,r) 不同奇偶时，这个永远是偶数，答案就是 (0)。
当 (l,r) 同奇偶时，当且仅当 (i) 和 (l) 同奇偶时是奇数。两个树状数组维护即可。
时间复杂度 (O((n+q)log n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=200020,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,q,a[maxn],b[2][maxn];
inline void update(int *b,int p,int v){
for(int i=p;i<=n;i+=i&-i) b[i]^=v;
}
inline int query(int *b,int p){
int s=0;
for(int i=p;i;i-=i&-i) s^=b[i];
return s;
}
inline int query(int *b,int l,int r){
return query(b,r)^query(b,l-1);
}
int main(){
n=read();q=read();
FOR(i,1,n) update(b[i%2],i,a[i]=read());
while(q--){
int op=read(),x=read(),y=read();
if(op==1){
update(b[x%2],x,a[x]^y);
a[x]=y;
}
else{
if((y-x)%2==1) puts("0");
else printf("%d
",query(b[x%2],x,y));
}
}
}
[eJOI2019] 挂架（*）
看看样例解释找规律，然后就是普及组模拟了。
具体一点，每次特判 (kle 2)，然后后面会分成长度为 (2^1,2^2,2^3dots) 的段，每段会加上 (2^{n-2},2^{n-3},2^{n-4},dots)。
找到 (k) 所在那段，加上，减去左端点，接着做。
时间复杂度看实现，反正瞎写都能过。（给自己的垃圾 (O(nlog k)) 找借口）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1000100,mod=1000000007;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,pw[maxn],ans;
ll k;
int main(){
n=read();k=read();
pw[0]=1;
FOR(i,1,n) pw[i]=2*pw[i-1]%mod;
while(k){
if(k==1){ans=(ans+1)%mod;break;}
if(k==2){ans=(ans+1+pw[n-1])%mod;break;}
ll tmp=2;
int cur=n-1;
while(tmp<k) tmp*=2,cur--;
ans=(ans+pw[cur])%mod;
k-=tmp/2;
}
printf("%d
",ans);
}
[eJOI2019] T 形覆盖（*）
部分分启发意义很大。
第一个包，两两独立，很好做。
第二个包，对于相邻的显然只有一种方法，否则还是独立的。
第三个包，对于只有一个顶点相邻的，虽然有两种方法，但是覆盖到的格子完全一样。那么我们对每个八连通块分开考虑，八连通块之间独立。
只剩下 (x_i=x_j,|y_i-y_j|=2) 或者 (|x_i-x_j|=2,y_i=y_j) 了，其它的上面讨论过了。
我们考虑先把其它的都确定了，然后最后剩下一堆无法确定的。把满足上面那条式子的两点连个边，然后考虑每个联通块。
如果一个联通块是树，(c) 个点，那么除掉 (c) 个中心，还剩 (3c+1) 个格子。所以选择最小的一个格子不选即可。手玩发现肯定能还原放的方法。
如果一个联通块是基环树，那么还剩 (3c) 个格子，都得选。
如果都不是，那么剩余不到 (3c) 个格子，一定无解。
注意当有中心在边界上或者与已经被覆盖的格子相邻时，还有一点点区别，不过问题不大。
时间复杂度 (O(nm))。
由于菜，写的又臭又长。
写的时候可以这样写：每覆盖一个格子，它周围的 T 中心都处理一下（此时对于这个 T 中心合法方案不超过一种），递归下去。这样细节会少一点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1000100,mod=998244353,d1[4][2]={{0,1},{0,-1},{-1,0},{1,0}},d2[4][2]={{1,1},{-1,-1},{-1,1},{1,-1}},d3[4][2]={{0,2},{0,-2},{2,0},{-2,0}};
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,m,k,ans,cnt,mn;
int *a[maxn],*tp[maxn],*vis[maxn];
bool *bl[maxn];
inline void nsol(){puts("No");exit(0);}
void work2(int,int);
void work(int x,int y,int d){
if(tp[x][y]!=-1 && tp[x][y]!=d) nsol();
if(tp[x][y]==d) return;
tp[x][y]=d;
FOR(i,0,3) if(i!=d){
int tx=x+d1[i][0],ty=y+d1[i][1];
if(tx<1 || tx>n || ty<1 || ty>m || vis[tx][ty]!=-1) nsol();
ans+=a[tx][ty];
vis[tx][ty]=i^1;
work2(tx,ty);
}
}
void work2(int x,int y){
FOR(i,0,3) if(i!=vis[x][y]){
int tx=x+d1[i][0],ty=y+d1[i][1];
if(bl[tx][ty]) work(tx,ty,i^1);
}
}
void dfs(int x,int y,int lx,int ly){
cnt+=2;
tp[x][y]=-2;
FOR(i,0,3){
int tx=x+d3[i][0],ty=y+d3[i][1];
if(tx<1 || tx>n || ty<1 || ty>m || tp[tx][ty]>=0 || !bl[tx][ty]) continue;
cnt--;
if(tp[tx][ty]==-1) dfs(tx,ty,x,y);
}
FOR(i,0,3){
int tx=x+d1[i][0],ty=y+d1[i][1];
if(tx<1 || tx>n || ty<1 || ty>m || vis[tx][ty]!=-1){
if(vis[tx][ty]!=-2) cnt-=2;
continue;
}
vis[tx][ty]=-2;
ans+=a[tx][ty];
mn=min(mn,a[tx][ty]);
}
}
int main(){
n=read();m=read();
FOR(i,0,n+1){
a[i]=new int[m+2];
bl[i]=new bool[m+2];
vis[i]=new int[m+2];
tp[i]=new int[m+2];
FOR(j,0,m+1){
a[i][j]=0;
bl[i][j]=false;
vis[i][j]=-1;
tp[i][j]=-1;
}
}
FOR(i,1,n) FOR(j,1,m) a[i][j]=read();
k=read();
while(k--){
int x=read()+1,y=read()+1;
ans+=a[x][y];
bl[x][y]=true;
vis[x][y]=-2;
FOR(i,0,3){
int tx=x+d1[i][0],ty=y+d1[i][1];
if(bl[tx][ty] && tp[x][y]==-1) work(x,y,i),work(tx,ty,i^1);
}
}
FOR(x,1,n) FOR(y,1,m) if(bl[x][y] && tp[x][y]==-1){
FOR(i,0,3){
int tx=x+d2[i][0],ty=y+d2[i][1];
if(bl[tx][ty] && tp[x][y]==-1){work(x,y,i);break;}
}
}
FOR(x,1,n) FOR(y,1,m) if(bl[x][y] && tp[x][y]==-1){
mn=1e9;cnt=0;
dfs(x,y,-1,-1);
if(cnt<0) nsol();
if(cnt==2) ans-=mn;
}
printf("%d
",ans);
FOR(i,0,n+1){
delete[] a[i];
delete[] bl[i];
delete[] vis[i];
delete[] tp[i];
}
}
[eJOI2019] 塔（*）
先特判 (n=1)。
如果第 (i) 次操作让 (l_i=1,r_i=i)，那么最后会得到 (2^{i-1})。
所以我们找到一个最小的 (m) 满足 (2^{m-1}ge n)，明显至少要 (m) 次操作。
而 (m) 次操作也是可以做到的。选一些 (l_i) 加一，发现会让最后一个数减掉 (2^{max(1,m-i-1)})。
要减哪些很好弄，正确性也显然。
时间复杂度 (O(Tlog n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int T,m,l[maxn],r[maxn];
ll n,tmp[maxn];
void solve(){
n=read();
if(n==1) return void(puts("0"));
m=0;
while(true){
l[++m]=1;
r[m]=m;
if(m==1) tmp[m]=1;
else tmp[m]=tmp[m-1]*2;
if(tmp[m]>=n) break;
}
n=tmp[m]-n;
reverse(tmp,tmp+m+1);
FOR(i,1,m-1) if(n>=tmp[i]) n-=tmp[i],l[i]++;
printf("%d
",m);
FOR(i,1,m) printf("%d %d
",l[i],r[i]);
}
int main(){
T=read();
while(T--) solve();
}
[eJOI2019] 矩形染色（*）
先考虑另一个问题：每次可以染一行或一列。
容易发现，要么所有行都选，要么所有列都选。因为如果有一行不选，那么为了把那行都染上色，只能所有列都选。有一列不选同理。
到这题我们也用类似的想法。
首先黑白染色，那么黑白部分独立。这样接下来看着会稍微舒服一些。下面以包括左上角的那部分为例。
我们稍微转个 45 度，然后会变成个形如这样的东西。
我们从左往右枚举哪些列没有被选。先判掉所有列都选了的情况。
(f_i) 表示考虑了前 (i) 列，第 (i) 列没有被选的最小代价。
转移枚举上一个没选的列 (j)，由于这个图很特殊，只需要知道 (j)，就能知道少选第 (i) 列就要多选哪些行。只不过情况有点多。
发现可以线段树优化，时间复杂度 (O((n+m)log(n+m)))。
代码很恶心。虽然可能纯粹是因为我菜而写得很丑。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=400040,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
struct segtree{
int n;
ll mn[maxn*4];
inline void pushup(int o){
mn[o]=min(mn[o<<1],mn[o<<1|1]);
}
void build(int o,int l,int r){
if(l==r) return void(mn[o]=1e18);
int mid=(l+r)>>1;
build(lson);build(rson);
pushup(o);
}
inline void build(int n){
build(1,1,n);
this->n=n;
}
void update(int o,int l,int r,int p,ll v){
if(l==r) return void(mn[o]=v);
int mid=(l+r)>>1;
if(mid>=p) update(lson,p,v);
if(mid<p) update(rson,p,v);
pushup(o);
}
inline void update(int p,ll v){
update(1,1,n,p,v);
}
ll query(int o,int l,int r,int ql,int qr){
if(l>=ql && r<=qr) return mn[o];
int mid=(l+r)>>1;
if(mid<ql) return query(rson,ql,qr);
if(mid>=qr) return query(lson,ql,qr);
return min(query(lson,ql,qr),query(rson,ql,qr));
}
inline ll query(int l,int r){
l=max(l,1);r=min(r,n);
if(l>r) return 1e18;
return query(1,1,n,l,r);
}
}t1,t2,t3;
int n,m,a[maxn],b[maxn];
ll f[maxn],g[maxn],apre[maxn],bpre[maxn];
ll work(int beg){
t1.build(n+m-1);t2.build(n+m-1);t3.build(n+m-1);
ll ans=0;
for(int i=beg;i<=n+m-1;i+=2){
ans+=b[i];
if(i<=m){
int l=m-i+1,r=m+i-1;
ll c=apre[r]-apre[max(0,l-2)];
f[i]=c+(i==1?0:bpre[i-2]);
f[i]=min(f[i],t1.query(1,i)+c+(i==1?0:bpre[i-2]));
t1.update(i,f[i]-c-bpre[i]);
t2.update(i,f[i]-apre[r]-bpre[i]);
t3.update(i,f[i]-bpre[i]);
}
else if(i<=n){
int l=i-m+1,r=m+i-1;
ll c=apre[r]-apre[max(0,l-2)];
f[i]=c+bpre[i-2];
f[i]=min(f[i],t3.query(1,l-m)+c+bpre[i-2]);
f[i]=min(f[i],t1.query(l-m+1,2*m-i)+c+bpre[i-2]);
f[i]=min(f[i],t2.query(2*m-i+1,i)+apre[r]+bpre[i-2]);
t2.update(i,f[i]-apre[r]-bpre[i]);
t3.update(i,f[i]-bpre[i]);
}
else{
int l=i-m+1,r=m+2*n-i-1;
ll c=apre[r]-apre[max(0,l-2)];
f[i]=c+bpre[i-2];
f[i]=min(f[i],t3.query(1,l-m)+c+bpre[i-2]);
f[i]=min(f[i],t1.query(l-m+1,m-l+1)+c+bpre[i-2]);
f[i]=min(f[i],t2.query(m-l+2,2*n-i)+apre[r]+bpre[i-2]);
f[i]=min(f[i],t3.query(2*n-i+1,i)+bpre[i-2]);
t3.update(i,f[i]-bpre[i]);
}
}
int upr=n+m-1;
if(upr%2!=beg%2) upr--;
for(int i=beg;i<=n+m-1;i+=2) ans=min(ans,f[i]+bpre[upr]-bpre[i]);
return ans;
}
int main(){
n=read();m=read();
FOR(i,1,n+m-1) a[i]=read();
FOR(i,1,n+m-1) b[i]=read();
if(n<m){
swap(n,m);
reverse(a+1,a+n+m);
}
FOR(i,1,n+m-1){
if(i==1) apre[i]=a[i],bpre[i]=b[i];
else apre[i]=apre[i-2]+a[i],bpre[i]=bpre[i-2]+b[i];
}
printf("%lld
",work(1)+work(2));
}
[eJOI2019] 箭头国探险（*）
这个中二的题目名是我自己弄的
我们把对 ((i,j)) 的转向变成走到 ((i,j)) 上再转。
(f_{i,j}) 表示走到 ((i,j)) 的最小代价。
用最短路转移。
时间复杂度 (O(nmlog nm))，写四个队列也可以做到 (O(nm)) 带个不小的常数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=505,MAXN=maxn*maxn,MAXM=MAXN*4,mod=998244353,d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
struct node{
int u,d;
bool operator<(const node &nd)const{return d>nd.d;}
};
int n,m,tp[128],el,head[MAXN],to[MAXM],nxt[MAXM],w[MAXM],dis[MAXN];
char mp[maxn][maxn];
priority_queue<node> pq;
inline int id(int x,int y){
return 1ll*(x-1)*m+y;
}
inline void add(int u,int v,int w_){
to[++el]=v;nxt[el]=head[u];head[u]=el;w[el]=w_;
}
int main(){
tp['E']=0;tp['S']=1;tp['W']=2;tp['N']=3;
n=read();m=read();
FOR(i,1,n) scanf("%s",mp[i]+1);
FOR(i,1,n) FOR(j,1,m) if(mp[i][j]!='X') FOR(k,0,3){
int x=i+d[k][0],y=j+d[k][1];
if(x<1 || x>n || y<1 || y>m) continue;
add(id(i,j),id(x,y),(k-tp[mp[i][j]]+4)%4);
}
FOR(i,1,n*m) dis[i]=1e9;
dis[1]=0;
pq.push((node){1,0});
while(!pq.empty()){
int u=pq.top().u,d=pq.top().d;pq.pop();
if(d>dis[u]) continue;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]>d+w[i]) pq.push((node){v,dis[v]=d+w[i]});
}
}
printf("%d
",dis[id(n,m)]==1e9?-1:dis[id(n,m)]);
}