4
29
2015
0

HEOI2015(弃坑)

woc day2T1太难辣。。

弃坑了。。。想看D2T1的去吉利blog

 

兔子与樱花：

贪心，肯定从深度大的先合并，这样影响少，然后每个点选最小的儿子。。（口胡不会证）

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=2000005;

vector<int> Son[N];

int n,m,d[N],Ans,val[N];

void dfs(int u)
{
	for(int i=0;i<Son[u].size();i++)
		dfs(Son[u][i]),
		Son[u][i]=val[Son[u][i]];
	sort(Son[u].begin(),Son[u].end());
	for(int i=0;i<Son[u].size();i++)
		if(val[u]+Son[u][i]-1<=m)
			val[u]+=Son[u][i]-1,
			Ans++;
		else
			return;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	for(int u,i=1,k;i<=n;i++)
	{
		scanf("%d",&k);
		val[i]+=k;
		while(k--)
			scanf("%d",&u),
			Son[i].push_back(++u),
			d[u]=1;
	}
	for(int i=1;i<=n;i++)
		if(!d[i])
			dfs(i);
	cout<<Ans<<endl;
	return 0;
}

公约数数列：

我会分块我自豪！每块建个hash表，查询如果这段gcd都相同就在hash表里找，否则就暴力，显然gcd只会有log种，最多log次，时间复杂度$q*n^{0.5}log^2 n$跑的还很快shenmegui啊。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

typedef long long LL;

const int N=100005,Mod=357;

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

struct H_SH
{
	int tot,num[Mod],G[Mod],next[Mod];
	void clear()
	{
		tot=0;
		memset(G,0,sizeof(G));
	}
	
	bool operator[](int x)
	{
		int k=x%Mod;
		for(int i=G[k];i;i=next[i])
			if(num[i]==x)
				return 1;
		return 0;
	}
	
	void insert(int x)
	{
		if((*this)[x])
			return;
		int k=x%Mod;
		num[++tot]=x;next[tot]=G[k];G[k]=tot;
	}
}H[Mod];

int Lzz[N],_xor[N],_gcd[N],Ed[Mod],n,q,flag,Ans,sz,K;

LL x;

void build(int t)
{
	int l=Ed[t-1]+1,r=Ed[t];
	H[t].clear();
	H[t].insert(_xor[l]=_gcd[l]=Lzz[l]);
	for(int i=l+1;i<=r;i++)
		_gcd[i]=gcd(_gcd[i-1],Lzz[i]),
		H[t].insert(_xor[i]=_xor[i-1]^Lzz[i]);
}

void find(int t,int Lxor,int Lg)
{
	int l=Ed[t-1]+1,r=Ed[t];
	for(int i=l;i<=r;i++)
		if((_xor[i]^Lxor)*(LL)gcd(Lg,_gcd[i])==x)
		{
			flag=1;
			Ans=i;
			return;
		}
}

void solve()
{
	flag=0;
	int Lxor=0,Lg=0;
	for(int i=1;i<=K;i++)
	{
		int g=gcd(Lg,_gcd[Ed[i]]);
		if(g!=Lg)
		{
			find(i,Lxor,Lg);
			if(flag)
				break;
		}
		else if(x%g==0&&((x/g)^Lxor)<=2000000000&&H[i][(x/g)^Lxor])
		{
			find(i,Lxor,Lg);
			break;
		}
		Lxor^=_xor[Ed[i]];
		Lg=g;
	}
	if(flag)
		printf("%d\n",Ans-1);
	else
		puts("no");
}

int main()
{
	scanf("%d",&n);
	sz=sqrt(n)+1;
	K=(n-1)/sz+1;
	for(int i=1;i<=n;i++)
		scanf("%d",Lzz+i);
	for(int i=1;i<=K;i++)
		Ed[i]=min(Ed[i-1]+sz,n),
		build(i);
	scanf("%d",&q);
	while(q--)
	{
		char s[10];
		scanf("%s",s);
		if(s[0]=='M')
		{
			int x,y;
			scanf("%d%d",&x,&y);
			Lzz[++x]=y;
			build((x-1)/sz+1);
		}
		else
			scanf("%lld",&x),
			solve();
	}
	return 0;
}

定价：

枚举末尾0个数，算下就好

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef long long LL;
 
LL Ans,Num;
 
LL work(LL k)
{
    while(k%10==0)
        k/=10;
    LL w=-(k%10==5);
    while(k)
        k/=10,w+=2;
    return w;
}
 
void Update(LL k)
{
    LL w=work(k);
    if(w<Num||(w==Num&&k<Ans))
        Ans=k,Num=w;
}
 
int main()
{
    LL t,l,r;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&l,&r);
        Ans=l;Num=work(l);
        for(LL w=1;w<=r;w*=10)
        {
            LL k=l/(w*10)*(w*10);
            while(k<l)
                k+=w*10;
            if(k<=r)
                Update(k);
            k=l/(w*10)*(w*10)+w*5;
            while(k<l)
                k+=w*10;
            if(k<=r)
                Update(k);
        }
        cout<<Ans<<endl;
    }
    return 0;
}

小Z的房间：

$Matrix-tree$定理裸上

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef long long LL;
 
const int N=15,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},Mod=1000000000;
 
int d[N*N][N*N],id[20][20],n,m,k;
 
#define Pr pair<int,int>
#define x first
#define y second
 
Pr operator-(const Pr& A,const Pr& B)
{
    return Pr((A.x-B.x+Mod)%Mod,(A.y-B.y+Mod)%Mod);
}
 
Pr operator*(const Pr& A,const int& B)
{
    return Pr(A.x*(LL)B%Mod,A.y*(LL)B%Mod);
}
 
int Gauss(int n)
{
    int flag=1;
    for(int i=1;i<=n;i++)
    {
        int p;
        for(p=i;p<=n;p++)
            if(d[p][i])
                break;
        if(p!=i)
        {
            flag=-flag;
            for(int j=i;j<=n;j++)
                swap(d[i][j],d[p][j]);
        }
        for(int j=i+1;j<=n;j++)
        {
            int Lzz=d[i][i],ZZl=d[j][i];
            Pr A=Pr(1,0),B=Pr(0,1);
            while(ZZl)
                swap(A,B),
                B=B-A*(Lzz/ZZl),
                swap(Lzz,ZZl),
                ZZl%=Lzz,
                flag=-flag;
            for (int k=i;k<=n;k++)
            {
                int Yjc=d[i][k],Cjy=d[j][k];
                d[i][k]=((LL)A.x*Yjc+(LL)A.y*Cjy)%Mod;
                d[j][k]=((LL)B.x*Yjc+(LL)B.y*Cjy)%Mod;
            }
        }
    }
    int S=flag;
    for(int i=1;i<=n;i++)
        S=S*(LL)d[i][i]%Mod;
    return (S+Mod)%Mod;
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char s[15];
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            if(s[j]=='.')
                id[i][j]=++k;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(id[i][j])
                for(int k=0;k<4;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(id[x][y])
                        d[id[i][j]][id[i][j]]++,
                        d[id[i][j]][id[x][y]]--;
                }
    cout<<Gauss(k-1)<<endl;
    return 0;
}

最短不公共子串：

出题人和yjc一样啊。。。。bfs4合1！如果要求B是子串就用后缀自动机，要求B是子序列就是一个记录$suc[a][b]$表示a后第一个字符b的位置的东西

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
const int N=2005;
 
namespace SAM
{
    int Son[N*2][26],pre[N*2],len[N*2],last=1,now=1;
     
    void Extend(int x)
    {
        int p=last,np=last=++now;
        len[np]=len[p]+1;
        for(;p&&!Son[p][x];p=pre[p])
            Son[p][x]=np;
        if(!p)
            pre[np]=1;
        else
        {
            int q=Son[p][x];
            if(len[q]==len[p]+1)
                pre[np]=q;
            else
            {
                int nq=++now;
                memcpy(Son[nq],Son[q],sizeof Son[nq]);
                len[nq]=len[p]+1;
                pre[nq]=pre[q];
                pre[q]=pre[np]=nq;
                for(;p&&Son[p][x]==q;p=pre[p])
                    Son[p][x]=nq;
            }
        }
    }
}
 
int sucA[N][26],sucB[N][26],n,m,vis[N][N*2];
 
char A[N],B[N];
 
struct Lzz
{
    int x,y,l;
     
    Lzz(int a=0,int b=0,int l=0):x(a),y(b),l(l){}
};
 
int OrzLzz1()
{
    queue<Lzz> Orz;
    for(int i=0;i<n;i++)
        Orz.push(Lzz(i,1,0));
    while(!Orz.empty())
    {
        Lzz w=Orz.front();
        Orz.pop();
        if(w.x==n)
            continue;
        int next=SAM::Son[w.y][A[w.x+1]-'a'];
        if(!next)
            return w.l+1;
        if(vis[w.x+1][next]!=1)
            vis[w.x+1][next]=1,
            Orz.push(Lzz(w.x+1,next,w.l+1));
    }
    return -1;
}
 
int OrzLzz2()
{
    queue<Lzz> Orz;
    for(int i=0;i<n;i++)
        Orz.push(Lzz(i,0,0));
    while(!Orz.empty())
    {
        Lzz w=Orz.front();
        Orz.pop();
        if(w.x==n)
            continue;
        int next=sucB[w.y][A[w.x+1]-'a'];
        if(!next)
            return w.l+1;
        if(vis[w.x+1][next]!=2)
            vis[w.x+1][next]=2,
            Orz.push(Lzz(w.x+1,next,w.l+1));
    }
    return -1;
}
 
int OrzLzz3()
{
    queue<Lzz> Orz;
    Orz.push(Lzz(0,1,0));
    while(!Orz.empty())
    {
        Lzz w=Orz.front();
        Orz.pop();
        for(int i=0;i<26;i++)
        {
            int nextx=sucA[w.x][i],nexty=SAM::Son[w.y][i];
            if(!nextx)
                continue;
            if(!nexty)
                return w.l+1;
            if(vis[nextx][nexty]!=3)
                vis[nextx][nexty]=3,
                Orz.push(Lzz(nextx,nexty,w.l+1));
        }
    }
    return -1;
}
 
int OrzLzz4()
{
    queue<Lzz> Orz;
    Orz.push(Lzz(0,0,0));
    while(!Orz.empty())
    {
        Lzz w=Orz.front();
        Orz.pop();
        for(int i=0;i<26;i++)
        {
            int nextx=sucA[w.x][i],nexty=sucB[w.y][i];
            if(!nextx)
                continue;
            if(!nexty)
                return w.l+1;
            if(vis[nextx][nexty]!=4)
                vis[nextx][nexty]=4,
                Orz.push(Lzz(nextx,nexty,w.l+1));
        }
    }
    return -1;
}
 
int main()
{
    gets(A+1);
    n=strlen(A+1);
    gets(B+1);
    m=strlen(B+1);
    for(int i=1;i<=m;i++)
        SAM::Extend(B[i]-'a');
    for(int i=n-1;~i;i--)
        memcpy(sucA[i],sucA[i+1],sizeof sucA[i]),
        sucA[i][A[i+1]-'a']=i+1;
    for(int i=m-1;~i;i--)
        memcpy(sucB[i],sucB[i+1],sizeof sucB[i]),
        sucB[i][B[i+1]-'a']=i+1;
    printf("%d\n%d\n%d\n%d\n",OrzLzz1(),OrzLzz2(),OrzLzz3(),OrzLzz4());
    return 0;
}
Category: My Oi,My Life | Tags: HEOI 逗比 | Read Count: 2034
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com