高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=3107

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
391549	Liu_Ts	3107	Accepted	1272 kb	64 ms	C++/Edit	1466 B	2013-04-16 11:59:41

 

题意

给三个数a,b,c。

构造三个新二进制数A,B,C，要求每个数与原数中1的个数相同，且满足A+B=C。

求满足条件的最小的C

题解

DP，f[t][i][j][k][p]，表示枚举到第t位，A已放i个1，B已放j个1，C已放k个1，若p=0，表示该状态无进位；否则表示有进位。

 

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
const int N=31;
int n,a,b,c,f[2][N][N][N][2];
inline int get(int x)
{
	int s;
	for(s=0;x;x>>=1)
		if(x&1) s++;
	return s;
}
void init()
{

	int x,y,z;scanf("%d%d%d",&x,&y,&z);
	a=get(x);b=get(y);c=get(z);
	x=max(x,max(y,z));
	for(n=0;x;x>>=1) n++;
}

void work(int &a,int b)
{
	if(a==-1) a=b;
	else a=min(a,b);
}

int main()
{
	init();
	memset(f,-1,sizeof(f));
	f[0][0][0][0][0]=0;
	int cur=0;
	for(int t=0;t<n;t++,cur^=1)
		for(int i=0;i<=min(t,a);i++)
			for(int j=0;j<=min(t,b);j++)
				for(int k=0;k<=min(t,c);k++)
				{
					if(f[cur][i][j][k][0]!=-1)
					{
						int now=f[cur][i][j][k][0];
						work(f[cur^1][i][j][k][0],now);
						if(i+1<=a&&k+1<=c) work(f[cur^1][i+1][j][k+1][0],now+(1<<t));
						if(i+1<=a&&j+1<=b) work(f[cur^1][i+1][j+1][k][1],now);
						if(j+1<=b&&k+1<=c) work(f[cur^1][i][j+1][k+1][0],now+(1<<t));
					}
					if(f[cur][i][j][k][1]!=-1)
					{
						int now=f[cur][i][j][k][1];
						work(f[cur^1][i][j][k+1][0],now+(1<<t));
						if(i+1<=a) work(f[cur^1][i+1][j][k][1],now);
						if(j+1<=b) work(f[cur^1][i][j+1][k][1],now);
						if(i+1<=a&&j+1<=b&&k+1<=c)  work(f[cur^1][i+1][j+1][k+1][1],now+(1<<t));
					}
				}				
	printf("%d\n",f[cur][a][b][c][0]);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3108

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
391508	Liu_Ts	3108	Accepted	892 kb	412 ms	C++	730 B	2013-04-16 10:40:15

 

题意

原图中的一条边为新图中的一个点，原图中两条相接的边为新图中的一条边，即a→b为点ab，a→b→c为ab→bc。

题目要求根据新图判断是否存在一个原图。

题解

如果在新图中存在 i->k 和 j->k

那么在原图里一定是这样的

所以我们可以发现，如果存在i->k和j->k

但只存在i->t或j->t其中之一，则新图不合法。

O(N^3)验证

 

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=301;
int n,m;bool a[N][N];

inline void init()
{
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=0;i<m;i++)
		scanf("%d%d",&x,&y),a[x][y]=1;
}

inline bool check()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			bool f1=0,f2=0;
			for(int k=0;k<n;k++)
			{
				if(a[i][k]&&a[j][k]) f1=true;
				if(a[i][k]!=a[j][k]) f2=true;
				if(f1&&f2) return 0;
			}
		}
	return 1;
}

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		init();
		if(check()) puts("Yes");
		else puts("No");
	}
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3122

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
391145	Liu_Ts	3122	Accepted	9100 kb	1488 ms	C++	2158 B	2013-04-15 17:39:23

 

题意

已知Xi+1=(aXi + b)mod p；

给定X1，a，b，p(质数），t

求第一个满足Xn=t的n

题解

把原式化开，得

Xn=[a^(n-1)*X1+b*(a^(n-2)+a^(n-3)+..+a^0)]mod p;

分情况讨论

①X1=t时，ans=1；

②a=0时，

    1.b=t时,ans=2;

    2.b!=t时,ans=-1;

③a=1时，

    Xn=[X1+b*(n-1)]mod p=t

    移向之后，相当于求xb+yp=(t-X1)mod p;

    扩展gcd，ans=x+1;

④a>1时，

    Xn=[a^(n-1)*X1+b*(a^(n-1)-1)/(a-1)]mod p

    设c=(a-1)在模p意义下的逆元，即c=(a-1)^(p-2);

    Xn=[a^(n-1)*X1+bc*(a^(n-1)-1)]mod p

    化简得Xn=[(X1+bc)*a^(n-1)-bc]mod p=t

    令q=X1+bc，t`=(t+bc)mod p,

    移向后相当于求[q*a^(n-1)]mod p=t'

    接下来我的做法是，先求xq+yp=t'的解x；

    问题变为求a^x` mod p=x，ans=x`+1。就和山东11年的计算器那题一样了。

 

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;
typedef long long ll;
const int H=1000001;
int f[H],r[H];
ll p,a,b,x1,x,y,t;
 
ll km(ll a,ll k)
{
    if(!a) return 0;
    ll t=a,q=1;
    while(k)
    {
        if(k&1) q=((q%p)*(t%p))%p;
        t=((t%p)*(t%p))%p;
        k=k>>1;
    }
    return q;
}
void gcd(ll a,ll b,ll c)
{
    if(!b)
        if(!(c%a))
        {
            x=c/a;y=0;
            return;
        }
        else
        {
            x=-1;return;
        }
    gcd(b,a%b,c);
    if(x==-1) return;
    ll t=y;y=x-((a/b)*y);x=t;
}
       
void work1()
{
    t=(t-x1+p)%p;
    x=y=0;
    gcd(b,p,t);
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
        x++;
    }
    printf("%lld\n",x);
}
void work2()
{
    ll c=km(a-1,p-2);
    t=(t+((b*c)%p))%p;
    ll q=(x1+((b*c)%p))%p;
    x=y=0;
    gcd(q,p,t);
    if(x==-1)
    {
        puts("-1");return;
    }
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
    }
    int m=int(floor(sqrt(p)+1)),b=km(a,p-1-m);;
    memset(f,255,sizeof(f));
    memset(r,255,sizeof(r));
    ll now=1;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1) h=(h+1)%H;
        f[h]=now;r[h]=i;now=now*a%p;
    }
    now=x%p;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1)
        {
            if(f[h]==now)
            {
                printf("%d\n",i*m+r[h]+1);
                return;
            }
            h=(h+1)%H;
        }
        now=now*b%p;
    }
    puts("-1");
}
 
void work()
{
    if(x1==t){puts("1");return;}
    if(a==0)
    {
        if(b==t) puts("2");
        else puts("-1");
        return;
    } 
    if(a==1)
    {
        work1();
        return;
    }
    work2();
}
     
int main()
{
    int T;scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
        work();
    }
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3124

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
391083	Liu_Ts	3124	Accepted	14000 kb	1572 ms	C++	1383 B	2013-04-15 16:26:40

 

题意

一棵树，求直径和有多少条边一定在直径上。

题解

我就不说我省选有多傻叉了。

首先DFS求出直径，

显然一定在直径上的边一定是任意一条直径上连续的一段。

所以我们遍历求出的直径（红色+蓝色）上的每个点x，

如果以这个点为起点，在不访问直径上的点的情况下，

求出一条最长链，图中的黑色

如果等于蓝色的长度或红色的长度，那么这段蓝色或红色就不是一定在直径上。

这样不断缩小左右端点，剩下的链上的边就是答案

 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200011,M=N*2;
int v[M],w[M],next[M],head[N],k=1;
long long d[N],dep[N],ans1,tmp;
int n,pre[N],A,B,leaf;bool vis[N];

void add(int x,int y,int z)
{
	v[++k]=y;w[k]=z;next[k]=head[x];head[x]=k;
	v[++k]=x;w[k]=z;next[k]=head[y];head[y]=k;
}

void dfs(int x,int fa)
{
	pre[x]=fa;
	if(dep[x]>tmp)
		tmp=dep[x],leaf=x;
	for(int i=head[x];i;i=next[i])
		if(v[i]!=fa)
			dep[v[i]]=dep[x]+w[i],dfs(v[i],x);
}

void  find(int x,int fa)
{
	tmp=max(tmp,d[x]);
	for(int i=head[x];i;i=next[i])
		if((v[i]!=fa) && (!vis[v[i]]))
			d[v[i]]=d[x]+w[i],find(v[i],x);
}

int main()
{
	scanf("%d",&n);int x,y,z;
	for(int i=1;i<n;i++)
		scanf("%d%d%d",&x,&y,&z),add(x,y,z);
	tmp=dep[1]=0;dfs(1,0);A=leaf;
	tmp=dep[A]=0;dfs(A,0);B=leaf;
	ans1=tmp;
	printf("%lld\n",ans1);
	memset(vis,0,sizeof(vis));
	for(int i=B;i;i=pre[i]) vis[i]=1;
	bool flag=1;int left=A,right=B;
	for(int i=B;i;i=pre[i])
	{
		long long ldist=dep[i],rdist=ans1-dep[i];
		tmp=d[i]=0;find(i,0);
		if((tmp==ldist) && flag) 
			left=i,flag=0;
		if(tmp==rdist) right=i;
	}
	int ans2=0;
	for(int i=right;i!=left;i=pre[i]) ans2++;
	printf("%d\n",ans2);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=2600

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
382037	Liu_Ts	2600	Accepted	1976 kb	484 ms	C++	541 B	2013-04-02 07:54:49

 

题意

n片稻田，分别位于x[i],建一个谷仓，使得总代价不大于b的情况下，控制的稻田最多，总代价定义为所有稻田到谷仓的距离和。

题解

IOI最弱题。

1.对于选出的稻田集合S，建在他们的中位数的位置最优

2.显然选连续的稻田更优，此时cost可以前缀和O(1)

3.所以O(n)扫过去就可以了

 

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100001;
int a[N],l,r,ans;
long long s[N],b;
long long cost(int l,int r)
{
	int m=l+r>>1;
	long long tmp=(m-l+1)*a[m]-(s[m]-s[l-1])+(s[r]-s[m])-(r-m)*a[m];
	return tmp;
}
int main()
{
	scanf("%d%d%lld",&r,&l,&b);
	for(int i=1;i<=r;i++)
		scanf("%d",a+i),s[i]=s[i-1]+a[i];
	for(int i=1,j=1;j<=r;j++)
	{
		while(cost(i,j)>b) i++;
		ans=max(ans,j-i+1);
	}
	printf("%d\n",ans);
}