POI2010
T1.Guilds 并查集判断有没有孤立点即可
#include<cstdio>
#define N 200100
int n,m,i,x,y,p,q,fa[N],sz[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uni(int x,int y){
p=find(x);q=find(y);
if(sz[p]>sz[q])p^=q^=p^=q;
sz[q]+=sz[p];fa[p]=q;
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)fa[i]=i,sz[i]=1;
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),uni(x,y);
for(i=1;i<=n;i++)if(sz[i]==1&&fa[i]==i)return puts("NIE"),0;
puts("TAK");
}
T2.Railway（未完成） 这题是双栈排序的加强版，不过我连双栈排序都没做过，就先把双栈排序做了
#include<cstdio>
#include<algorithm>
#define N 1111
#define M 2222222
using namespace std;
int n,i,j,tot,tp1,tp2,now,col[N],mi[N],a[N],fir[N],la[M],ne[M],st1[N],st2[N];bool flag;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int co){
col[x]=co;
for(int i=fir[x];i;i=ne[i])if(!col[la[i]])dfs(la[i],3-co);else if(col[la[i]]==col[x])flag=1;
}
int main(){
scanf("%d",&n);flag=0;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(mi[n]=a[n],i=n-1;i>=1;i--)mi[i]=min(mi[i+1],a[i]);
for(i=1;i<n;i++)for(j=i+1;j<n;j++)if(mi[j+1]<a[i]&&a[i]<a[j])ins(i,j),ins(j,i);
for(i=1;i<=n;i++)if(!col[i])dfs(i,1);
if(flag)return puts("0"),0;
for(now=1,i=1;i<=n;i++){
if(col[i]==1)st1[++tp1]=a[i],printf("a ");else st2[++tp2]=a[i],printf("c ");
for(;(tp1&&st1[tp1]==now)||(tp2&&st2[tp2]==now);now++){
if(tp1&&st1[tp1]==now)tp1--,printf("b");
if(tp2&&st2[tp2]==now)tp2--,printf("d");
if(now!=n)printf(" ");
}
}
}
可以考虑维护每个点的前向边和后向边，前向边还是比较好维护的，线段树搞搞就可以啦，后向边挺难写的，要线段树上挂链。。贴个标程算了
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
const int MAXN=100057;
const int INF=1000000000;
int poc[MAXN],rev[MAXN],mini[MAXN],c[MAXN];
int n;
vector<int> tab[MAXN];
bool niet=false;
struct Drzewo {
Drzewo* left;
Drzewo* right;
int key;
int dist;
};
inline Drzewo* create(int x) {
Drzewo* d = new Drzewo;
d->key = x;
d->dist = 1;
d->left = NULL;
d->right = NULL;
return d;
}
inline int top(Drzewo* d) {
return (d==NULL)?(0):(d->key);
}
inline int dist(Drzewo* d){
return (d==NULL)?(0):(d->dist);
}
Drzewo* merge(Drzewo* a, Drzewo* b) {
if (a==NULL) return b;
if (b==NULL) return a;
// a!=NULL && b!=null
if (top(b)<top(a)) swap(a,b);
a->left = merge(a->left,b);
if (dist(a->left) > dist(a->right) ) swap(a->right,a->left);
if (a->right==NULL) a->dist = 0; else a->dist = 1+a->right->dist;
return a;
}
Drzewo* deleteMin(Drzewo* d) {
if (d!=NULL) {
Drzewo* tmp = merge(d->left,d->right);
free(d);
return tmp;
}
return NULL;
}
inline bool isEmpty(Drzewo* d) {
return (d==NULL);
}
void paint(int p,int colour) {
c[p]=colour;
for(int i=0;i<(int)tab[p].size();i++) {
if (c[tab[p][i]]==0) paint(tab[p][i],colour%2+1); else
if (c[tab[p][i]]!=(colour%2+1)) niet=true;
}
}
bool checkOut() {
stack<int> st[2];
for(int i=0;i<2;i++) st[i].push(-1);
int passed = 1;
for(int i=1;i<=n;i++) {
if (c[i]!=0) st[c[i]-1].push(poc[i]); else return false;
bool change = true;
while (change) {
change = false;
for(int j=0;j<2;j++) {
while (st[j].top()==passed) {
passed++;
st[j].pop();
change = true;
}
}
}
}
return (passed==n+1);
}
int main() {
Drzewo* stos[MAXN];
int head = -1;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&poc[i]);
rev[poc[i]]=i;
}
int prev=INF;
for(int i=n;i>=1;i--) {
mini[i]=prev;
prev=min(prev,poc[i]);
}
for(int i=1;i<=n;i++) {
int d=poc[i], e=mini[i];
Drzewo* tmp = create(poc[i]);
bool finished = false;
while (head!=-1 && !finished) {
Drzewo* v=stos[head];
int val=top(v);
if (val<d) {
tab[i].push_back(rev[val]);
tab[rev[val]].push_back(i);
tmp=merge(tmp,v);
head--;
} else finished = true;
}
finished = false;
head++; stos[head]=tmp;
while (head!=-1 && !finished) {
tmp=stos[head]; head--;
while (!isEmpty(tmp) && (top(tmp)<e)) tmp=deleteMin(tmp);
if (!isEmpty(tmp)) {
head++; stos[head] = tmp;
finished = true;
}
}
}
for(int i=1;i<=n;i++) c[i]=0;
for(int i=1;i<=n;i++) if (c[i]==0) paint(i,1);
niet = checkOut();
if (!niet) printf("NIE\n"); else {
printf("TAK\n");
for(int i=1;i<=n;i++) printf("%d ",c[i]);
printf("\n");
}
}
T3 Beads 这种题目是常规字符串算法无法胜任的，要用HASH大法，两边各统计哈希值前缀和，然后求的时候从$1$到$n$暴力求，求的复杂度$O(1)$，要求$\sum_{i=1}^n\frac{n}{i}$次,也就是$nlgn$次，然后再排序去重，复杂度$O(nlg^2n)$
#include<cstdio>
#include<algorithm>
typedef unsigned long long LL;
#define S 999983LL
#define N 1111111
using namespace std;
int n,i,j,top,cnt,ans,tp,q[N];
LL w,a[N],s1[N],s2[N],st[N];
int main(){
scanf("%d",&n);w=1;
for(i=1;i<=n;i++)scanf("%llu",&a[i]),s1[i]=s1[i-1]*S+a[i];
for(i=n;i;i--)s2[i]=s2[i+1]*S+a[i];
for(i=1;i<=n;i++){
top=0;w=w*S;
for(j=1;j+i-1<=n;j+=i)st[++top]=min(s1[j+i-1]-s1[j-1]*w,s2[j]-s2[j+i]*w);
sort(st+1,st+top+1);cnt=unique(st+1,st+top+1)-(st+1);
if(cnt>ans)ans=cnt,q[tp=1]=i;else if(ans==cnt)q[++tp]=i;
}
printf("%d %d\n",ans,tp);
for(i=1;i<=tp;i++)if(i==tp)printf("%d",q[i]);else printf("%d ",q[i]);
}
T4 Divine divisor 首先Miller-Rabin算法的基础是费马小定理，大概就是n是一个奇素数，$1\leq a<n,a^{n-1}\ mod\ n=1$
可以用这个定理为基础进行Miller-Rabin判断一个大于等于3的数n是否为质数，然后进行T次如下操作：
随机选择一个整数a(2≤a≤n-2),计算y=a^r mod n,然后如果y^(n-1) mod n=1则不是负数，否则继续判断，若T次结束就是素数
这题大概就是弄出$10^6$以内的素数，然后剩下的数只可能是$p$，$p^2$或$pq$，把$p$和$p^2$搞出来后互相gcd，然后剩下的要不然是素数要不然是不同的素数相乘，统计一下答案就可以了。。不过挺难弄的，不想搞了。。大概后面有几个点错了、、一开始是米勒罗宾写炸没快速乘。。改了也WA。。
然后改了一下写的姿势还是WA，和正确的程序对比下发现Millar-Rabin是错的。。看来4行的米勒罗宾是不靠谱的，就拉了个正常的米勒罗宾，然后就过了。。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define N 1111111
using namespace std;
typedef long long LL;
int i,j,n,w,now,res,ans,cnt,ww,prime[N],c[N];
LL g,z[N],W[]={0,2,3,11,67};bool f[N];
struct BI{
int a[500],h;
BI operator +(const BI &x)const{
BI ret;int p=0;
memset(ret.a,0,sizeof(ret.a));
for(int i=1;i<=h;i++){
ret.a[i]=a[i]+x.a[i]+p;
p=ret.a[i]/10;
ret.a[i]=ret.a[i]%10;
}
ret.h=h;if(p>0)ret.a[++ret.h]=p;
return ret;
}
}ANS;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
LL mul(LL a,LL b,LL M){
LL ans=0;
for(;b;b>>=1){
if(b&1)ans=(ans+a)%M;
a=(a+a)%M;
}
return ans;
}
LL pow(LL a,LL b,LL M){
LL ans=1;
for(;b;b>>=1){
if(b&1)ans=mul(ans,a,M);
a=mul(a,a,M);
}
return ans;
}
bool mr(LL n){
if (n<2)return 0;if (n==2)return 1;if (!(n&1))return 0;
LL d=n-1,r=0;
while(!(d&1))r++,d>>=1;
for (int a=1;a<=4;a++){
LL now=W[a];if(now==n)continue;
LL v=pow(now,d,n);if(v==1||v==n-1)continue;
bool find=0;
for(int b=1;b<r&&!find;b++){
v=mul(v,v,n);
if(v==n-1)find=1;
}
if(!find)return 0;
}
return 1;
}
void ql(){cnt++;for(int k=1;k<=n;k++)while(z[k]%g==0)z[k]/=g,c[cnt]++;}
int main(){
for(w=1000000,i=2;i<=w;i++){
if(!f[i])prime[++cnt]=i;
for(j=1;j<=cnt&&i*prime[j]<=w;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld",&z[i]);
for(j=1;j<=cnt;j++)while(z[i]%(LL)prime[j]==0)c[j]++,z[i]/=(LL)prime[j];
}
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(z[i]!=1&&z[j]!=1&&z[i]!=z[j]){
g=gcd(z[i],z[j]);
if(g!=1){
ql();
if(z[i]!=1)g=z[i],ql();
if(z[j]!=1)g=z[j],ql();
}
}
for(i=1;i<=n;i++)if(z[i]!=1){
g=ceil((LL)sqrt(z[i]));
if(g*g==z[i])ql();
}
for(i=1;i<=n;i++)if(mr(z[i]))g=z[i],ql(),ww++;
for(i=1;i<=cnt;i++)if(c[i]>ans)ans=c[i],res=1;else if(c[i]==ans)res++;
for(i=1;i<=n;i++)if(z[i]!=1){
now=0;
for(j=i;j<=n;j++)if(z[j]==z[i])now++;
if(now>ans)ans=now,res=1;else if(now==ans)res+=2;
}
printf("%d\n",ans);
for(ANS.h=1,ANS.a[1]=1,i=0;i<res;i++)ANS=ANS+ANS;
for(ANS.a[1]--,i=ANS.h;i;i--)printf("%d",ANS.a[i]);
}
T5 Intelligence test 写了个set结果T了，然后卡了卡常又T了，然后加了个读入优化才卡过
#include<cstdio>
#include<set>
using namespace std;
int T,n,i,x,m,pos;bool flag;char ch;
set<int> st[1000011];
void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}
int main(){
read(n);
for(i=1;i<=n;i++){
read(x);
st[x].insert(i);
}
read(T);
while(T--){
read(m);
pos=0;flag=0;
for(i=1;i<=m;i++){
read(x);
if(!flag)if(st[x].size()==0){flag=1;}
else if(*--st[x].end()<=pos){flag=1;}
else pos=*st[x].upper_bound(pos);
}
if(!flag)puts("TAK");else puts("NIE");
}
}
T6 Antisymmetry 把Manacher的判断条件稍微改一下就可以了，顺便把Manacher背了一下，差不多背会了，不过交的时候没有注意奇数长度的是不合法的WA了一发
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500010
using namespace std;
typedef long long LL;
LL ans;int n,i,l,mx,p,r[N*2],ma[N*2];char s[N];
int main(){
scanf("%d%s",&n,s);
ma[l++]=7;ma[l++]=3;for(i=0;i<n;i++)ma[l++]=2*(s[i]-'0'+1),ma[l++]=3;
for(i=1;i<l;i+=2){
r[i]=mx>i?min(r[2*p-i],mx-i):1;
for(;ma[i+r[i]]+ma[i-r[i]]==6;r[i]++);
if(i+r[i]>mx)mx=i+r[i],p=i;
}
for(i=3;i<l;i+=2)ans+=(LL)(r[i]-1)/2;
printf("%lld",ans);
}
T7 Hamsters 首先可以求出每两个串的最长后缀接前缀，这可以用HASH完成，这样$dis[i][j]=len[j]-cal(i,j)$，注意自己接自己的时候不能$cal(i,j)$不能为$len[j]$，然后可以通过类似Floyd+快速幂的方法快速求解，时间复杂度$O(kn+n^3lgm)$，学会了动态开数组的新姿势
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
typedef unsigned long long LL;
#define N 203
#define M 100100
#define S 999983LL
using namespace std;
int n,m,i,j,k,len[N];
LL miv,*h1[N],pow[M],f[N][N],g[N][N],ans[N][N];char s[M];
int cal(int x,int y){
for(int i=min(len[x],len[y])-(len[y]<=len[x]);i;i--)if(h1[x][len[x]]-h1[x][len[x]-i]*pow[i]==h1[y][i])return i;
return 0;
}
int main(){
scanf("%d%d",&n,&m);miv=1e18;
for(i=1;i<=n;i++){
scanf("%s",s+1);len[i]=strlen(s+1);
h1[i]=new LL[len[i]+1];h1[i][0]=0;
for(j=1;j<=len[i];j++)h1[i][j]=h1[i][j-1]*S+(LL)(s[j]-'a'+1);
}
for(pow[0]=1,i=1;i<=100000;i++)pow[i]=pow[i-1]*S;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=len[j]-cal(i,j);
memset(ans,0x3f,sizeof ans);m--;
for(i=1;i<=n;i++)ans[i][i]=0;
for(;m;m>>=1){
if(m&1){
memset(g,0x3f,sizeof g);
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=min(g[i][j],ans[i][k]+f[k][j]);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)ans[i][j]=g[i][j];
}
memset(g,0x3f,sizeof g);
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=min(g[i][j],f[i][k]+f[k][j]);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=g[i][j];
}
for(i=1;i<=n;i++)for(j=1;j<=n;j++)miv=min(miv,ans[i][j]+len[i]);
printf("%llu",miv);
}
T8 Blocks 首先如果一个区间的平均值大于k即是合法的，对于每个$k$我们要求出这个最大的区间，可以用$sum[i]=sum[i-1]+a[i]-k$，这样维护一个单调下降的sum单调栈，就可以在$O(n)$的时间内求出答案
#include<cstdio>
#include<algorithm>
#define N 1111111
using namespace std;
int n,m,i,k,top,ans,q[N];
long long a[N],sum[N];
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
while(m--){
top=ans=0;scanf("%d",&k);
for(i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-k;
for(i=1;i<=n;i++)if(sum[q[top]]>sum[i])q[++top]=i;
for(i=n;i;i--){
for(;top&&sum[i]>=sum[q[top-1]];top--);
ans=max(ans,i-q[top]);
}
!m?printf("%d",ans):printf("%d ",ans);
}
}
T9 Sheep 首先如果一条对角线两边的羊都是偶数就是合法的，但如果暴力判断很明显会超时，可以以每个牧场边上的点为极点进行极角排序，然后就可以判断每条对角线是否合法了，接下来只要一个简单的区间DP就行啦，时间复杂度$O(nmlgm+n^3)$
#include<cstdio>
#include<algorithm>
#define N 620
#define M 20020
using namespace std;
int n,k,m,i,j,l,p,MO,f[N][N];bool v[N][N],ok;
struct EG{int x,y;}eg[M],q[N],st;
int multi(EG a,EG b,EG c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
bool cmp(EG a,EG b){return multi(st,a,b)<0;}
int main(){
scanf("%d%d%d",&n,&m,&MO);
for(i=1;i<=n;i++)scanf("%d%d",&q[i].x,&q[i].y);
for(i=1;i<=m;i++)scanf("%d%d",&eg[i].x,&eg[i].y);
for(i=1;i<=n;i++){
st=q[i];sort(eg+1,eg+m+1,cmp);
for(k=1,j=i%n+1,ok=1;k<=m;ok=!ok,k++)
for(;i!=j&&(p=multi(st,q[j],eg[k]))<=0;j=j%n+1)if(p<0)v[i][j]=ok;
for(;i!=j;j=j%n+1)v[i][j]=ok;
}
for(i=1;i<=n;i++)f[i][i%n+1]=1;
for(l=2;l<=n;l++)
for(i=1;i<=n;i++){
j=(i+l-1)%n+1;
for(k=1;k<=n;k++)if(v[i][k]&&v[k][j])f[i][j]=(f[i][j]+f[i][k]*f[k][j])%MO;
}
printf("%d",f[1][n]);
}
T10 Teleportation 首先很明显这是一个分层的图，每一层内互相连，然后层之间互相连，于是这个图最多只有四层
为了方便，先把和1相连的点放到第一层中，把和2相连的点放到第二层中，然后可以证明把剩下的点放到第一层或第二层不是好的选择，因为如果不放可以和他们的点全连，而且自己也可以连
剩下的点如果和第一层的点连过，就和所有第一层的点连，如果和第二层的点连过，就和所有第二层的点连，然后全部互相连，这样就能得到最优的答案啦
#include<cstdio>
#include<algorithm>
#define N 40040
#define M 1001000
using namespace std;
int n,m,i,a[M],b[M],f[N];bool f1[N],f2[N];long long ans,s1,s2,s3;
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
scanf("%d%d",&a[i],&b[i]);
if(a[i]<=2)f[b[i]]=a[i];
if(b[i]<=2)f[a[i]]=b[i];
}
for(i=3;i<=n;i++)if(!f[i])s3++;else if(f[i]==1)s1++;else s2++;
for(ans=(s3*(s3-1)+s1*(s1+1)+s2*(s2+1))/2,i=1;i<=m;i++){
if(f[a[i]])if(f[a[i]]==1)f1[b[i]]=1;else f2[b[i]]=1;
if(f[b[i]])if(f[b[i]]==1)f1[a[i]]=1;else f2[a[i]]=1;
}
for(i=3;i<=n;i++)if(!f[i])if(f1[i])ans+=s1;else if(f2[i])ans+=s2;else ans+=max(s1,s2);
printf("%lld",ans-m);
}
T11 Monotonicity（双倍） 要用线段树维护DP，有点贪心的思想，不管符号的限制，每次尽量取最优的，不知道为何这样是对的。。
#include<cstdio>
#include<algorithm>
#define N 500100
using namespace std;
int n,k,w,i,ans,c,p[N],a[N],r[N],xd[N*2];
char s[3],ch;
struct XD{
struct T{int l,r,mv;}t[N*8];
void build(int k,int l,int r){
t[k].l=l;t[k].r=r;
if(l==r)return;
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void ins(int k,int x,int z){
int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
t[k].mv=max(t[k].mv,z);
if(l==r)return;
if(x<=mid)ins(k<<1,x,z);else ins(k<<1|1,x,z);
}
int find(int k,int x,int y){
if(x>y)return 0;
int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
if(x<=l&&r<=y)return t[k].mv;
if(x>mid)return find(k<<1|1,x,y);
else if(y<=mid)return find(k<<1,x,y);
else return max(find(k<<1,x,mid),find(k<<1|1,mid+1,y));
}
}dw,up;
void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}
int main(){
read(n);read(k);w=1000000;
for(i=1;i<=n;i++)read(a[i]);
dw.build(1,1,w);up.build(1,1,w);
for(i=0;i<k;i++){
scanf("%s",s);
if(s[0]=='<')p[i]=1;else if(s[0]=='>')p[i]=2;else p[i]=3;
}
for(i=1;i<=n;i++){
r[i]=1+max(xd[a[i]],max(dw.find(1,1,a[i]-1),up.find(1,a[i]+1,w)));
ans=max(r[i],ans);c=p[(r[i]-1)%k];
if(c==1)dw.ins(1,a[i],r[i]);else if(c==2)up.ins(1,a[i],r[i]);else xd[a[i]]=r[i];
}
printf("%d",ans);
}
T12 The Minima Game $dp[i]$表示在$i$先手比后手多取的值，$dp[i]=max(a[j+1]-dp[j])$，单调维护$a[j+1]-dp[j]$的值即可
#include<cstdio>
#include<algorithm>
#define N 1111111
using namespace std;
int n,i;long long ma,a[N],dp[N];
int main(){
scanf("%d",&n);for(i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+n+1);
for(ma=a[1],i=1;i<=n;i++)dp[i]=ma,ma=max(ma,a[i+1]-dp[i]);
printf("%lld",dp[n]);
}
T13 翻译都没有一定很难
T14 Frogs 由于第0-k近的点范围是单调增的，找第$k$近点就可以$O(n)$维护，然后就可以求出后一步走到的点，可这题如果直接倍增会MLE我也是醉了，然后压一下还是TLE也没办法。。然后必须用类似快速幂的方法做到$O(n)$的空间，没读入优化9.5S卡过
#include<cstdio>
#define N 1000100
typedef long long LL;int n,k,i,j,l,r,pos,ne[N][61];LL m,a[N];
int main(){
scanf("%d%d%lld",&n,&k,&m);for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(l=1,r=k+1,ne[1][0]=k+1,i=2;i<=n;i++){
for(;r<n&&a[r+1]-a[i]<a[i]-a[l];l++,r++);
ne[i][0]=a[r]-a[i]>a[i]-a[l]?r:l;
}
for(j=1;j<=60;j++)for(i=1;i<=n;i++)ne[i][j]=ne[ne[i][j-1]][j-1];
for(i=1;i<=n;i==n?printf("%d",pos):printf("%d ",pos),i++)for(pos=i,j=0;j<=60;j++)if(m&(1LL<<j))pos=ne[pos][j];
}
#include<cstdio>
#define N 1000100
typedef long long LL;int n,k,i,j,l,r,pos,ne[N],f[N],g[N],t[N];LL m,a[N];
int main(){
scanf("%d%d%lld",&n,&k,&m);for(i=1;i<=n;i++)scanf("%lld",&a[i]),g[i]=i;
for(l=1,r=f[1]=k+1,i=2;i<=n;i++){
for(;r<n&&a[r+1]-a[i]<a[i]-a[l];l++,r++);
f[i]=a[r]-a[i]>a[i]-a[l]?r:l;
}
for(;m;m>>=1){
if(m&1){
for(i=1;i<=n;i++)t[i]=f[g[i]];
for(i=1;i<=n;i++)g[i]=t[i];
}
for(i=1;i<=n;i++)t[i]=f[f[i]];
for(i=1;i<=n;i++)f[i]=t[i];
}
for(i=1;i<=n;i++)printf("%d%c",g[i],i==n?'\n':' ');
}
T15 最短5K，蒟蒻无能为力
T16 Bridges 觉得这是一个欧拉回路判定问题，搜了下发现混合图欧拉回路判定需要网络流，首先所有点入度-出度必须是2的倍数，然后对于入不敷出的点连汇点/2，源点入度多的/2，然后对于每条无向边先设好方向，连边流量为1，就可以达到无向边效果，检查是否满流即可，这题再加个二分答案就行了，不过我WA了也不想调了
#include<cstdio>
#include<cstring>
#define CL(a) memset(a,0,sizeof(a))
#define inf 1e9
#define N 2222
#define M 8888
int n,m,i,u,s,t,l,r,mid,now,tot,tmp,flow,ext,ans,a[N],b[N],c[N],d[N],fir[N],dist[N],cur[N],pre[N],numb[N],in[N],va[M],ne[M],la[M];
void ins(int x,int y,int z){
la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;
la[++tot]=x;va[tot]=0;ne[tot]=fir[y];fir[y]=tot;
}
int ISAP(){
CL(numb);CL(dist);CL(pre);
for(i=1;i<=t;i++)cur[i]=fir[i];u=s;numb[0]=t;
while(dist[s]<t){
if(u==t){
now=inf;
for(i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]]){
va[cur[i]]-=now;
va[cur[i]^1]+=now;
}
flow+=now;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&dist[la[i]]+1==dist[u])break;
if(i){
cur[u]=i;
pre[la[i]]=u;
u=la[i];
}else{
if(0==--numb[dist[u]])break;
for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])
if(dist[la[i]]<tmp&&va[i])tmp=dist[la[i]];
++numb[dist[u]=tmp+1];
if(u!=s)u=pre[u];
}
}
return flow;
}
bool ok(int w){
tot=1;CL(fir);CL(in);CL(va);CL(la);CL(ne);s=n+1;t=s+1;ext=0;
for(i=1;i<=m;i++){
if(c[i]<=w&&d[i]<=w)in[a[i]]++,in[b[i]]--,ins(a[i],b[i],1);
else if(c[i]<=w)in[a[i]]--,in[b[i]]++;
else if(d[i]<=w)in[b[i]]--,in[a[i]]++;
else return 0;
}
for(i=1;i<=n;i++)if(in[i]&1){return 0;}else if(in[i]>0)ins(s,i,in[i]/2),ext+=in[i]/2;else if(in[i]<0)ins(i,t,(-in[i])/2);
return ISAP()>=ext;
}
int main(){
freopen("mos2b.in","r",stdin);freopen("mos.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
ans=-1;l=0;r=1000;
while(l<=r){
mid=l+r>>1;
if(ok(mid))ans=mid,r=mid-1;else l=mid+1;
}
if(ans==-1)puts("NIE");else printf("%d",ans);
}
T17 Pilots 维护两个单调队列即可
#include<cstdio>
#include<algorithm>
#define N 3001000
using namespace std;
int n,k,i,h1,t1,h2,t2,t,ans,a[N],q1[N],q2[N];
int main(){
scanf("%d%d",&k,&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
h1=1;h2=1;t1=0;t2=0;t=1;
for(i=1;i<=n;i++){
for(;h1<=t1&&a[i]>=a[q1[t1]];t1--);
for(;h2<=t2&&a[i]<=a[q2[t2]];t2--);
q1[++t1]=i;q2[++t2]=i;
while(a[q1[h1]]-a[q2[h2]]>k)if(q1[h1]<q2[h2])t=q1[h1++]+1;else t=q2[h2++]+1;
ans=max(ans,i-t+1);
}
printf("%d",ans);
}
感觉收获还是挺大的，切这一套题我学会了大素数判定，背会了Manacher，加深了对字符串HASH的理解，学会了使用set的正确姿势，还学会了一些倍增的黑科技，以及混合图欧拉回路的判定
评论 (0)
