caozy623's Blog

这是很早之前开的坑……最近准备持续更新= =

基本上每十次左右的比赛，我会调出一些我不太会但是难度我还能接受的记录进来。。。（一般都是比赛的时候不会然后赛后补的）

先把这几天要填的坑填完……T T

题意 by hongrock （语文水平及表达水平不高借鉴别人的题目翻译……）

题目就是N个点的无向图，先给出M条边，这M条边使得任意两点间要么不连通，要么仅有唯一的路径相连。

两个点如果连通就说明它们在同一个区域。

然后Q个询问

1 x，输出x所在区域的最长路径；

2 x y，如果x和y在同一区域则忽略，否则合并两个区域，并且合并之后的新区域的最长路径应该是最短的。

题意：

你可以叉掉某些点，使这些点不连通。给定n，问至少要叉多少点，可以使离原点欧几里得距离（平时说的距离）在n之内的整点与比n

距离大的整点都不四联通。

第一遍题意读过去有点难懂。。。我也解释的不是很清楚。。。自己动手画一下就知道了。

实际上画了你就会发现，其实就是画一个意原点为圆心，半径为n的圆。然后做到里面的整点和外面的整点不四联通就行。

那么只要涂掉里面相对最外层的所有整点即可。。。因为斜边（半径）确定，只要枚举一下直角边即可（枚举一条，另一条可以确

定）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 100010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
	char x=getchar();
	while(!(x>='a'&&x<='z'))x=getchar();
	while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}

int main()
{
    ll n;
    ll last=0,ans=0;
    scanf("%I64d",&n);
    if(n==0) puts("1");
    else
    {
        for(ll d=n;d>=0;d--)
        {
            ll r=(ll)sqrt(n*n-d*d)+(ll)1;
            //printf("%I64d\n",r);
            ans+=max((ll)1,r-last);
            last=r;
        }
        ans=(ll)4*ans-(ll)4;
        printf("%I64d\n",ans);
    }
    return 0;
}

题意：

有一些袋鼠，将A袋鼠装进B的口袋当且仅当Va*2<=Vb，每只袋鼠只能装一只。问最少可以剩下多少袋鼠能被看到。（就是说装进口袋里就看不见了）

这道题也能作为div1 A……挺水的，只需要sort一下然后贪心即可，因为最少只能是[n/2]+1。所以从i从n/2枚举到1，j从n开始枚举到n/2+1。然后简单贪心一下即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 1000010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
#define REP( i, n ) for ( int i = 1; i <= n; i ++ )
#define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
#define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
#define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
#define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
#define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
#define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
#define RST( a ) memset ( a, 0, sizeof ( a ) )
#define CLR( a, x ) memset ( a, x, sizeof ( a ) )
#define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
	char x=getchar();
	while(!(x>='a'&&x<='z'))x=getchar();
	while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int n;
int a[maxn];
int main()
{
    n=read();
    REP(i,n) a[i]=read();
    sort(a+1,a+n+1);
    int j=n;
    int ans=n;
    DWN(i,1,(n/2))
    if(a[i]*2<=a[j])
    {
        ans--;
        j--;
    }
    printf("%d\n",ans);
    return 0;
}

怎么说呢……这不就是一道双取方格数的题目，记得不错提高组考过差不多的题目，不过这题的范围更强一点。这样就必须优化到3维。

其实确定了前三个数，最后一个数是可以算出来的。。。所以就解决了。注意特判下一些特殊情况……这里如果来回路过同一个方格是

不能取两次的。别的没什么了。。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 100010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
	char x=getchar();
	while(!(x>='a'&&x<='z'))x=getchar();
	while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int f[305][305][305];
int n;
int a[305][305];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    f[i][j][k]=-inf;
    f[1][1][1]=a[1][1];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int p=1;p<=n;p++)
	{
		int q=i+j-p;
		if (q<=0) continue;
		if (i!=1&&p!=1)
		{
			int k=f[i-1][j][p-1]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
		if (i!=1&&q!=1)
		{
			int k=f[i-1][j][p]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
		if (j!=1&&p!=1)
		{
			int k=f[i][j-1][p-1]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
		if (j!=1&&q!=1)
		{
			int k=f[i][j-1][p]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
	}
    printf("%d\n",f[n][n][n]);
    return 0;
}

题意：

求给定数列中含有的波动子序列长度的最大值。（如2 3 2 3即为波动数列，注意不一定连续）

这题可以乱搞，也可以贪心，也可以DP。

我这里用的是DP的方法。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 100010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
char x=getchar();
while(!(x>='a'&&x<='z'))x=getchar();
while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int n,ans=0;
int a[maxn];
int f[4001][4001];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int last=0;
        for(int j=0;j<i;j++)
        {
            f[i][j]=f[j][last]+1;
            if(a[i]==a[j]) last=j;
            ans=max(f[i][j],ans);
        }
    }
    printf("%d\n",ans);
    return 0;
}