8
20
2014
0

关于Codeforces的文章标题格式的声明

我一般采用以下格式：

Codeforces Round#XXXY

XXX为比赛序号，

然后Y是题号。

鉴于div1和div2有重，我将会以div2的序号为准。（我是蒟蒻= =）

然后div1的D和E会写成S和SS。

没了……T T 

Category: 未分类 | Tags:
8
19
2014
0

Codeforces Round#230C

题意：

你可以叉掉某些点，使这些点不连通。给定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;
}
Category: codeforces | Tags: 数学
8
19
2014
0

Codeforces Round#219C

题意：

有一些袋鼠，将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;
}
Category: codeforces | Tags: 贪心
8
19
2014
0

Codeforces Round#131E

怎么说呢……这不就是一道双取方格数的题目，记得不错提高组考过差不多的题目，不过这题的范围更强一点。这样就必须优化到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;
}
Category: codeforces | Tags: DP
8
19
2014
0

Codeforces Round#156C

题意：

求给定数列中含有的波动子序列长度的最大值。（如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;
}

 

Category: codeforces | Tags:
8
19
2014
0

Codeforces Round#131D

题意：
给定数n和10个数的数组a，求满足以下条件的数的个数
1、数的长度不超过n
2、这个数不含前导0
3、数字i至少出现a[i]次

典型的数位DP，我们设f[i][j]为前i位数使用了j-9的数字能得到的数的个数
首先枚举长度len，对j的不同情况进行讨论：
1、j=9，此时若len>=a[9]，那么f[len][9]=1否则为0
2、0<j<9，此时考虑枚举数字j时，j+1到9已经枚举完毕。此时j的个数可以为k(a[j]<=k<=len)，
对于每个k放置在数列中的方法显然有C(len,k)种。那么状态转移方程即为f[len][j]+=f[len-k][j+1]*c[len][k]
其中c是组合数。
3、j=0，此时因为不能有前导0，所以对于0来说放置的方法只有len-1种，个数上限也是len-1，别的细节和第二种情况的是差不多的。
中间注意步步取模，注意是长度不超过n，所以最后输出sum（f[i][0]）{0<=i<=n}即可

 

#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)
#define hzy 1000000007
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();
}
ll f[110][10];
ll c[110][110];
int n;
int a[20];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<=9;i++)
    scanf("%d",&a[i]);
    for(int i=0;i<=n;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
        c[i][j]=(c[i-1][j-1]+c[i-1][j])%hzy;
    }
    //for(int i=1;i<=n;i++)
    //for(int j=1;j<=i;j++)
    //printf("%d\n",c[i][j]);
    for(int len=0;len<=n;len++)
    {
        if(len>=a[9]) f[len][9]=1;
        else f[len][9]=0;
        for(int j=8;j>=1;j--)
        for(int k=a[j];k<=len;k++)
        f[len][j]=(f[len][j]+f[len-k][j+1]*c[len][k])%hzy;
        for(int k=a[0];k<=len-1;k++)
        f[len][0]=(f[len][0]+f[len-k][1]*c[len-1][k])%hzy;
    }
    ll ans=0;
    for(int i=0;i<=n;i++)
    ans=(ans+f[i][0])%hzy;
    printf("%I64d\n",ans);
    return 0;
}
Category: codeforces | Tags: 数位DP

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