首页 > 代码库 > 20170116小测233
20170116小测233
更正：pdfT1(mex)中的前两个“她”误打成了“他”...
T1：mex
分析：
我们可以得到mex函数一个很有用的性质：左端点相同，右端点递增，mex递增...
所以我们可以O(n)滴求出mex(1,i)...然后我们维护左端点的位置，从1到n，每次左端点向右移动一位，就可以更新i+1到下一次a[i]出现的位置的mex函数，这样暴力修改是O(n^2)的，可以拿到60分...
如果要拿满分显然可以用线段树维护区间修改区间求和...
还有另一种代码短常数小的方法---递推...
记f[i]代表Σ(1<=x<=i)mex[x,i]我们可以通过上面那种性质得到f[i]是递增的...
所以可以根据f[i]间接推出f[i+1]，记第i个数为sa[i],显然只用考虑大于等于sa[i]的数j对f[i]=f[i-1]+？的影响,。如果j出现在1~i-1区间中，比较j最晚出现的位置与覆盖完全的1~j-1的最小位置的较小位置k，那么区间j的前一次出现的位置到k位置这个区间内所有点到i位置的值都+1.
代码：
（递推）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define int long long
using namespace std;
//mei yan ru chu,sui yue ru gu
const int maxn=500000+5;
int n,ans,a[maxn],p[maxn],mp[maxn],mex[maxn],nxt[maxn],vis[maxn],last[maxn];
inline void solve1(void){
for(int i=1;i<n;i++){
for(int j=i+1;j<nxt[i];j++)
if(mex[j]>a[i])
mex[j]=a[i];
for(int j=i+1;j<=n;j++)
ans+=mex[j];
}
printf("%lld\n",ans);
}
inline void solve2(void){
int now=0,pre;ans=0;
for(int i=1;i<=n;i++){
pre=p[a[i]];p[a[i]]=i;
for(int j=a[i];j<=n;j++){
if(j)
mp[j]=min(mp[j-1],p[j]);
else
mp[j]=p[j];
if(mp[j]>pre)
now+=mp[j]-pre;
else
break;
}
ans+=now;
}
printf("%lld\n",ans);
}
signed main(void){
// freopen("mex.in","r",stdin);
// freopen("mex.out","w",stdout);
scanf("%lld",&n);ans=0;
for(int i=1;i<=n;i++)
nxt[i]=n+1;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(a[i]>n)
a[i]=n;
if(last[a[i]])
nxt[last[a[i]]]=i,last[a[i]]=i;
else
last[a[i]]=i;
}int lala=0;
for(int i=1;i<=n;i++){
if(a[i]==lala){
vis[a[i]]=1;
while(vis[lala])
lala++;
}
else
vis[a[i]]=1;
mex[i]=lala;ans+=lala;
}
if(n<=1000)
solve1();
else
solve2();
fclose(stdin);fclose(stdout);
return 0;
}//Cap ou pas cap. Pas cap.
T2：game
分析：
有一些点，黑白染色，大概是二分图吧...
我们首先离散化坐标，对于每一个点，我们把行和列连边，然后每一次寻找一条交错路，黑白染色，然后再从这个点出发寻找交错路，相邻两次的交错路第一次的染色不同...
这样构造出来的答案差值最多是1...(因为我们是黑白交错染色...所以差值最大只可能是1)
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
//by NeighThorn
using namespace std;
//dan shi xiang si mo xiang fu,mu dan ting shang san sheng lu
const int maxn=600000+5;
int n,cntx,cnty,tot,hd[maxn],to[maxn],id[maxn],nxt[maxn],pos[maxn][2];
char ans[maxn];
map<int,int> mpx,mpy;
inline void add(int s,int x,int y){
to[tot]=y;id[tot]=s;nxt[tot]=hd[x];hd[x]=tot++;
}
inline void dfs(int x,int co){
for(int i=hd[x];i!=-1;hd[x]=i=nxt[i])
if(ans[id[i]]==0){
ans[id[i]]=co+‘0‘,dfs(to[i],co^1);return;
}
}
signed main(void){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);cntx=cnty=0;tot=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&pos[i][0],&pos[i][1]);
if(mpx.find(pos[i][0])==mpx.end())
mpx[pos[i][0]]=++cntx;
if(mpy.find(pos[i][1])==mpy.end())
mpy[pos[i][1]]=++cnty;
pos[i][0]=mpx[pos[i][0]],pos[i][1]=mpy[pos[i][1]];
}
memset(hd,-1,sizeof(hd));
for(int i=1;i<=n;i++)
add(i,pos[i][0],pos[i][1]+cntx),add(i,pos[i][1]+cntx,pos[i][0]);
for(int i=1;i<=cntx;i++){
int now=1;
for(int j=hd[i];j!=-1;hd[i]=j=nxt[j])
if(ans[id[j]]==0)
ans[id[j]]=now+‘0‘,dfs(to[j],now^1),now^=1;
}
for(int i=1;i<=n;i++)
printf("%c",ans[i]);puts("");
fclose(stdin);fclose(stdout);
return 0;
}//Cap ou pas cap. Pas cap.
T3：another
分析：
一看数据范围好大哦...其实没有什么用只要看是不是零就好...
把01矩阵看成邻接矩阵，然后A^k就是从i到j走k步的路径数，又因为至少有一个自环，所以如果整张图是一个强连通分量就是合法的...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//liang chen mei jing nai he tian,shang xin le shi shui jia yuan
const int maxn=1000+5;
int C,n,cas,cnt,tim,tail,flag,hd[maxn],to[maxn*maxn],mp[maxn],nxt[maxn*maxn],dfn[maxn],low[maxn],stk[maxn],instk[maxn];
inline int read(void){
char ch=getchar();int x=0;
while(!(ch>=‘0‘&&ch<=‘9‘))
ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)
x=x*10+ch-‘0‘,ch=getchar();
return x;
}
inline void add(int x,int y){
to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
}
inline void tarjan(int x){
dfn[x]=low[x]=++tim;stk[++tail]=x;instk[x]=1;
for(int i=hd[x];i!=-1;i=nxt[i]){
if(!dfn[to[i]])
tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
else if(instk[to[i]])
low[x]=min(dfn[to[i]],low[x]);
}
if(low[x]==dfn[x]){
int tmp;C++;
do{
tmp=stk[tail--];mp[tmp]=C;instk[tmp]=0;
}while(tmp!=x);
}
}
signed main(void){
freopen("another.in","r",stdin);
freopen("another.out","w",stdout);
cas=read();
while(cas--){
flag=1;C=cnt=tim=tail=0;
memset(mp,0,sizeof(mp));
memset(hd,-1,sizeof(hd));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(instk,0,sizeof(instk));
n=read();
for(int i=1;i<=n;i++)
for(int j=1,x;j<=n;j++){
x=read();
if(x)
add(i,j);
}
tarjan(1);
for(int i=1;i<=n&&flag;i++)
if(mp[i]!=mp[1])
flag=0;
puts(flag==0?"NO":"YES");
}
fclose(stdin);fclose(stdout);
return 0;
}//Cap ou pas cap. Pas cap.
By NeighThorn
20170116小测233
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。