NOI2014

Posted on Jun 09, 2015 By 二价氢

迟到近一年的题解～

Day1试题下载

Day2试题下载

Day1.

Task1 起床困难综合症

数位DP，找到每一位的最大值（即当这一位取0/1时这一位最大）

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=100005;
int op[maxn],num[maxn];
char sop[15];
int tnum;
int dp[32][2];
int n,m;
int mbit[32];
int gans[2];//gans[0]=小于m,gans[1]=等于m
int main()
{
    freopen("sleep.in","r",stdin);
    freopen("sleep.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%s%d",sop,&num[i]);
        if (sop[0]=='A')
            op[i]=1;
        else if (sop[0]=='O')
            op[i]=2;
        else if (sop[0]=='X')
            op[i]=3;
    }
    int tp;
    for (int i=0;i<31;i++)
    {
        dp[i][1]=1;dp[i][0]=0;
        for (int j=1;j<=n;j++)
        {
            tp=(num[j]>>i)&1;
            if (op[j]==1)
            {
                dp[i][0]&=tp;
                dp[i][1]&=tp;
            }else if (op[j]==2)
            {
                dp[i][0]|=tp;
                dp[i][1]|=tp;
            }else if (op[j]==3)
            {
                dp[i][0]^=tp;
                dp[i][1]^=tp;
            }
        }
    }
    int mbc=0;
    for (int i=0;i<31;i++)
    {
        mbit[i]=(m>>i)&1;
        if (mbit[i]==1)
            mbc=i;
    }
    for (int i=31;i>=0;i--)
    {
        if (mbit[i]==0)
        {
            if (i<mbc)
                gans[0]=max(((gans[0]<<1)|dp[i][0]),((gans[0]<<1)|dp[i][1]));
            else
                gans[0]=((gans[1]<<1)|dp[i][0]);
            gans[1]=((gans[1]<<1)|dp[i][0]);
        }else
        {
            if (i==mbc)
                gans[0]=((gans[1]<<1)|dp[i][0]);
            else
                gans[0]=max(max(((gans[0]<<1)|dp[i][0]),((gans[0]<<1)|dp[i][1])),((gans[1]<<1)|dp[i][0]));
            gans[1]=((gans[1]<<1)|dp[i][1]);
        }
    }
    printf("%d\n",max(gans[0],gans[1]));
    return 0;
}

Task2 魔法森林

正解是LCT，但是，氢酱不会LCT！

然而这题就不能做了么？不，我们发现只要维护联通性就够了，于是，维护联通性用啥？并查集啊！

倍增枚举\(A_i\)，发现\(\max\{B_i\}\)应该单调不增

用\(A_i\)与\(\max\{B_i\}\)求出新的\(\max\{B_i\}\)

效率出奇地高：

测试点 输入文件 测试结果 运行用时 内存消耗 得分
#1 forest1.in 答案正确 0.007 s 1.328 MB 5
#2 forest2.in 答案正确 0.002 s 1.328 MB 5
#3 forest3.in 答案正确 0.003 s 1.324 MB 5
#4 forest4.in 答案正确 0.007 s 1.324 MB 5
#5 forest5.in 答案正确 0.004 s 1.328 MB 5
#6 forest6.in 答案正确 0.008 s 1.328 MB 5
#7 forest7.in 答案正确 0.015 s 1.441 MB 5
#8 forest8.in 答案正确 0.025 s 1.434 MB 5
#9 forest9.in 答案正确 0.021 s 1.430 MB 5
#10 forest10.in 答案正确 0.025 s 1.430 MB 5
#11 forest11.in 答案正确 0.171 s 4.410 MB 5
#12 forest12.in 答案正确 0.140 s 4.414 MB 5
#13 forest13.in 答案正确 0.153 s 4.414 MB 5
#14 forest14.in 答案正确 0.141 s 4.414 MB 5
#15 forest15.in 答案正确 0.254 s 4.441 MB 5
#16 forest16.in 答案正确 0.241 s 4.453 MB 5
#17 forest17.in 答案正确 0.241 s 4.453 MB 5
#18 forest18.in 答案正确 0.205 s 4.453 MB 5
#19 forest19.in 答案正确 0.175 s 4.430 MB 5
#20 forest20.in 答案正确 0.347 s 4.480 MB 5 
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn=50005,maxm=100005;
struct edge
{
	int u,v,a,b;
	edge(){}
	edge(const int &_u,const int &_v,const int &_a,const int &_b):
		u(_u),v(_v),a(_a),b(_b){}
}e[maxm*2];
int te,h[maxn];
int n,m,tal;
int d[maxn],inq[maxn],al[maxm],alns[maxm];
//const int sn[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
//const int cn=16;
//queue<int> Q;
int fa(int u)
{
	return d[u]==u?d[u]:d[u]=fa(d[u]);
}
int comp(const edge &a,const edge &b)
{
	return a.b<b.b;
}
void uni(int u,int v)
{
	if (fa(u)!=fa(v))
		d[fa(u)]=d[v];
}
int spfa(int lima,int limb)
{
	int u,v,ve,maxr=0;
	for (int i=0;i<te;i++)
	{
		if (e[i].b>limb) break;
		if (e[i].a>lima) continue;
		if (fa(e[i].u)!=fa(e[i].v))
		{
			uni(e[i].u,e[i].v);
		}
		if (fa(n)==fa(1))
			return e[i].b;
	}
	return 0x3fffffff;
}
int getbl(int ai,int lb)
{
//	cerr<<ai<<" "<<lb<<endl;
	if (alns[ai])
		return alns[ai];
	for (int i=1;i<=n;i++) d[i]=i;
	int res=spfa(ai,lb);
	return (fa(n)==fa(1)?(alns[ai]=res):0x3fffffff);
}
int main()
{
	freopen("forest.in","r",stdin);
	freopen("forest.out","w",stdout);
	//memset(h,-1,sizeof(h));
	scanf("%d%d",&n,&m);
	int ta,tb,tu,tv;
	for (int i=0;i<m;i++)
	{
		scanf("%d%d%d%d",&tu,&tv,&ta,&tb);
		if (tv<tu) swap(tu,tv);
		if (tv==tu) continue;
		e[te++]=edge(tu,tv,ta,tb);
		al[tal++]=ta;
	}
	sort(&al[0],&al[tal]);
	sort(&e[0],&e[te],comp);
//	tal=unique(&al[0],&al[tal])-&al[0];
	int lima=0x3fffffff,limb=0x3fffffff,ans=0x3fffffff;
	for (int i=0;i<tal;i++)
	{
		limb=getbl(al[i],limb);
		for (int j=65536;j>0;j>>=1)
			if (i+j<tal && al[i+j]<maxn)
				if (getbl(al[i+j],limb)==limb)
					i+=j;
	}
	for (int i=0;i<maxn;i++)
		if (alns[i])
			ans=min(ans,i+alns[i]);
	printf("%d\n",ans==0x3fffffff?-1:ans);
	return 0;
}

Day2.

动物园

具体解法忘了，但是肯定是\(O(n)\)的

我们来看看哈希小王子我的做法吧

哈希啦，如果哈希的话这题就很明显了

有点超时，但是不要紧，这个是\(O(n \log n)\)的。炸不了多少。

#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ull;
 
const int mod=1000000007;
 
//bit
const int maxn=1000005;
int bit[maxn];
#define LOWBIT(x) (x&(-x))
void add(int x,int v)
{
    for (;x<maxn;x+=LOWBIT(x)) bit[x]+=v;
}
 
int sum(int x)
{
    int ret=0;
    for (;x>0;x-=LOWBIT(x)) ret+=bit[x];
    return ret;
}
 
const int maxl=1000005;
const ull hp=27;
ull H[maxl],P[maxl];
char s[maxl];int len;
 
inline ull get(int l,int r)
{
    return (H[r]-H[l-1]*P[r-l+1]);
}
inline int binary_find_max(int l,int r)
{
    int L=l,R=r,m;
    while (L+1 < R)
    {
        m=(L+R)>>1;
        if (get(1,m-l+1)==get(l,m))
            L=m;
        else
            R=m;
    }
    if (get(1,R-l+1)==get(l,R)) return R;
    return L;
}
void process()
{
    // O(n log n)
    scanf("%s",s+1);
    len=strlen(s+1);
    H[0]=0;
    memset(bit,0,sizeof(bit));
    for (int i=1;i<=len;i++) H[i]=H[i-1]*hp+(s[i]-'a'+1); //hash
    for (int i=2;i<=len;i++)
    {
        if (s[i]!=s[1]) continue;
        int Pl=i,Pr=min(len,i+i-2);
        int Pm=binary_find_max(Pl,Pr);
//      printf("-> %d %d\n",i,Pm);
//      add(1,1,len,Pl,Pm,1);
        add(Pl,1);add(Pm+1,-1);
    }
    long long ret=1,tmp;
    for (int i=1;i<=len;i++)
    {
        tmp=sum(i);
        (ret*=(tmp+1))%=mod;
    }
    printf("%lld\n",ret);
}
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    int t;
    scanf("%d",&t);
    P[0]=1;
    for (int i=1;i<maxl;i++) P[i]=P[i-1]*hp;
    while (t--)
        process();
    return 0;
}

##随机数生成器

水题，有\(O(n)\)做法考试时由于某些电脑配置太差而设置5s时限

我们发现取数有单调性，如果我们从小到大取，取了一个数，它的左下、右上都不会再取

标记即可，然后发现标记也有单调性，即如果向左下取，发现它被标记了，那么从它开始的左下均被标记，右上同理

#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=5005;
#define x first
#define y second
typedef pair<short,short> pss;
pair<short,short> Pos[maxn*maxn];
int Num[maxn*maxn];
int Out[maxn+maxn];
bool Used[maxn*maxn];
long long a,b,c,d,x0;
int N,M,Q;
long long Rand()
{
	return x0=(a*x0*x0+b*x0+c)%d;
}
const int getPos(int x,int y)
{
	return ((x-1)*M+y);
}
void Fill(int x,int y)
{
	int tpos;
	for (int i=x+1;i<=N;i++)
		for (int j=y-1;j>0;j--)
		{
			if (Used[tpos=getPos(i,j)]) break;
			Used[tpos]=1;
		}
	for (int i=x-1;i>0;i--)
		for (int j=y+1;j<=M;j++)
		{
			if (Used[tpos=getPos(i,j)]) break;
			Used[tpos]=1;
		}
}
int main()
{
	freopen("random.in","r",stdin);
	freopen("random.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld",&x0,&a,&b,&c,&d);
	scanf("%d%d%d",&N,&M,&Q);
	int num=0;
	for (int i=1;i<=N*M;i++) {Num[i]=i;swap(Num[i],Num[Rand()%i+1]);}
	int u,v;
	for (int i=1;i<=Q;i++)
	{
		scanf("%d%d",&u,&v);
		swap(Num[u],Num[v]);
	}
	for (int i=1;i<=N;i++)
		for (int j=1;j<=M;j++)
			Pos[Num[getPos(i,j)]]=pss(i,j);
	int tot=0;
	for (int i=1;i<=N*M;i++)
	{
		u=Pos[i].x;v=Pos[i].y;
		if (Used[getPos(u,v)])
			continue;
		Out[tot++]=i;
		Fill(u,v);
	}
	sort(&Out[0],&Out[tot]);
	for (int i=0;i<tot;i++)
		printf("%d%c",Out[i],(i==tot-1)?'\n':' ');
	return 0;
}