http://acm.bupt.edu.cn/onlinejudge/newoj/ShowContest/contest_detail.php?contest_id=373&contest_type=1

2013年3月21日
只有C题需要注意,若字符窜循环中用是strlen的会超时……

B题:  Good boy, laiyifa!(最短路)

#include <stdio.h>
#define INF 1001
int n,h;
int map[505][505],clost[505],vis[505];

int Dijsk(int s,int e){
	int i,j,k,Min;
	for(i=0;i<n;i++){
		clost[i]=map[s][i];
		vis[i]=0;
	}
	vis[s]=1;
	for(i=1;i<n;i++){
		Min=INF;
		for(j=0;j<n;j++){
			if(!vis[j] && clost[j]<Min){
				Min=clost[j];
				k=j;
			}
		}
		vis[k]=1;
		for(j=0;j<n;j++)
			if(!vis[j] && clost[j]>clost[k]+map[k][j])
				clost[j]=clost[k]+map[k][j];
	}
	return clost[e];
}

int main(){
	while(scanf("%d%d",&n,&h)!=EOF){
		int i,j,Min;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				scanf("%d",&map[i][j]);
				if(!map[i][j])
					map[i][j]=INF;
			}
		}
		Min=Dijsk(0,n-1)+Dijsk(n-1,0);
		if(Min<h)
			printf("%d\n",Min);
		else
			printf("-1\n");
	}
	return 0;
}

C题:Loli vs CET-4(暴力)

#include <string.h>
#include<stdio.h>
int cnt[30],num[30],Max;
char str[4][30][60];
void dfs(int i){
    int j,k;
    if(i==4){
        int sum=0;
        for(i=0;i<26;i++)
            sum+=cnt[i]*cnt[i];
        Max=Max>sum?Max:sum;
        return ;
    }
    for(j=0;j<num[i];j++){
        for(k=0;str[i][j][k];k++)
            cnt[str[i][j][k]-'a']++;
        dfs(i+1);
        for(k=0;str[i][j][k];k++)
            cnt[str[i][j][k]-'a']--;
    }
}
int main(){
    int cases;
    while(scanf("%d",&cases)!=EOF){
        while(cases--){
            int i,j;
            memset(cnt,0,sizeof(cnt));
            for(i=0;i<4;i++){
                scanf("%d",&num[i]);
                for(j=0;j<num[i];j++)
                    scanf("%s",&str[i][j]);
            }
            Max=-1;
            dfs(0);
            printf("%d\n",Max);
        }
    }
    return 0;
}
#include <stdio.h>
#include <string.h>

char str[5][35][60];
int num[5];
int res;

void dfs(int i, int t[]){
    if (i == 5){
        int sum = 0;
        for (int k='a' - 'a'; k<= 'z' - 'a'; k++)
            sum += t[k] * t[k];
        if (sum > res)
            res = sum;
        return;
    }

    for (int j=1; j<=num[i]; j++)
    {
        int time[30] = {0};
        int n = strlen(str[i][j]);
        for (int k=0; k<='z' - 'a'; k++)
            time[k] = t[k];
        for (int k=0; k<n; k++)
            time[str[i][j][k] - 'a'] ++;
        dfs(i + 1, time);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--){
        memset(str, 0, sizeof(str));
        res = 0;
        for (int i=1; i<5; i++){
            scanf("%d", &num[i]);
            getchar();
            for (int j=1; j<=num[i]; j++){
                scanf("%s", str[i][j]);
            }
        }
        int time[30] = {0};
        dfs(1, time);
        printf("%d\n", res);
    }
    return 0;
}
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char s1[40][60],s2[40][60],s3[40][60],s4[40][60];
int num[27];
int n1,n2,n3,n4;
int main()
{
    int t,i,j,k,maxx,ans,p,q,x,y;
    scanf("%d",&t);
    while(t--)
    {
        maxx=-1;
        scanf("%d",&n1);
        for(i=0;i<n1;i++) scanf("%s",s1[i]);
        scanf("%d",&n2);
        for(i=0;i<n2;i++) scanf("%s",s2[i]);
        scanf("%d",&n3);
        for(i=0;i<n3;i++) scanf("%s",s3[i]);
        scanf("%d",&n4);
        for(i=0;i<n4;i++) scanf("%s",s4[i]);
        for(i=0;i<n1;i++)
        {
            for(j=0;j<n2;j++)
            {
                for(k=0;k<n3;k++)
                {
                    for(q=0;q<n4;q++)
                    {
                        memset(num,0,sizeof(num));
                        for(y=0;s1[i][y];y++) num[s1[i][y]-'a']++;
                        for(y=0;s2[j][y];y++) num[s2[j][y]-'a']++;
                        for(y=0;s3[k][y];y++) num[s3[k][y]-'a']++;
                        for(y=0;s4[q][y];y++) num[s4[q][y]-'a']++;
                        for(p=0,ans=0;p<26;p++)
                            ans+=num[p]*num[p];
                        if(ans>maxx)
                            maxx=ans;
                    }
                }
            }
        }
        printf("%d\n",maxx);
    }
    return 0;
}
#include<stdio.h>
#include<string.h>
#include<math.h>
const int MN=60;
char s1[MN][MN],s2[MN][MN],s3[MN][MN],s4[MN][MN];
int hash1[30],hash2[30],hash3[30],hash4[30];

int main()
{
    int sum,ans;
    int T,n1,n2,n3,n4,i,j,k,t,x,y;
    scanf("%d",&T);
    while(T--)
    {
        sum=ans=0;
        scanf("%d",&n1);
        for(i=0;i<n1;i++) scanf("%s",s1[i]);
        scanf("%d",&n2);
        for(i=0;i<n2;i++) scanf("%s",s2[i]);
        scanf("%d",&n3);
        for(i=0;i<n3;i++) scanf("%s",s3[i]);
        scanf("%d",&n4);
        for(i=0;i<n4;i++) scanf("%s",s4[i]);

        for(i=0;i<n1;i++)
        {
            memset(hash1,0,sizeof(hash1));
            for(x=0;s1[i][x];x++) hash1[s1[i][x]-'a']++;
            for(j=0;j<n2;j++)
            {
                memset(hash2,0,sizeof(hash2));
                for(x=0;s2[j][x];x++) hash2[s2[j][x]-'a']++;
                for(k=0;k<n3;k++)
                {
                    memset(hash3,0,sizeof(hash3));
                    for(x=0;s3[k][x];x++) hash3[s3[k][x]-'a']++;
                    for(t=0;t<n4;t++)
                    {
                        sum=0;
                        memset(hash4,0,sizeof(hash4));
                        for(x=0;s4[t][x];x++) hash4[s4[t][x]-'a']++;
                        for(y=0;y<26;y++)
                        {
                            int tmp=hash1[y]+hash2[y]+hash3[y]+hash4[y];
                            sum+=(int)pow(tmp*1.0,2);
                        }
                        if(ans<sum) ans=sum;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

G题:3230391’s easy problem(打表)

#include <stdio.h>
#define MAX 1000005

int f[MAX];
int s[MAX];

int init()
{
    for (int i=1; i<MAX; i++)
        f[i]++;
    for (int i=2; i<MAX; i++)
        for (int j=i; j<MAX; j+=i)
            f[j]++;
    for (int i=1; i<MAX; i++)
        s[i] = s[i-1] + f[i];
    return 1;
}

int main()
{
    int n;
    init();
    while (scanf("%d", &n) && n)
    {
        printf("%d\n", s[n]);
    }
    return 0;
}

H:(二分)

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[3005];
int find(int l,int r,int x)
{
    int mid;
    if(l==r)
        if(x>a[l])
            return l+1;
        else
            return l;
    mid=(l+r)/2;
    if(x>a[mid])
        return find(mid+1,r,x);
    else
        return find(l,mid,x);
}
int main()
{
    int t,n,i,j,m;
    long long ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        ans=0;
        for(i=0;i<n;i++)
            for(j=i+1;j<n-1;j++)
            {
                m=find(j+1,n-1,a[i]+a[j]);
                ans+=m-j-1;
            }
        printf("%lld\n",ans);
    }
    return 0;
}

 

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
int a[3010];
int besearch(int l,int r,int tt)
{
    int mid;
    while(l+1<r)
    {
        mid=(r+l)>>1;
        if(a[mid]<tt) l=mid;
        else r=mid;
    }
    if(a[r]>=tt) return l;
    else return r;
}
int main()
{
    int t,n,i,j;
    scanf("%d",&t);
    while(t--)
    {
        ll sum=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
        sum+=besearch(j,n-1,a[i]+a[j])-j;
        printf("%lld\n",sum);
    }
    return 0;
}

I题:SQRT(乱搞)

#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
    long N,x,y,a;
    while(scanf("%ld",&N)!=EOF)
    {
         for(y=1;y<=N;y++)
         {
             a=(int)sqrt(N*y);
             if(a*a==N*y)
               break;
         }
        x=N+y+2*a;
        printf("%ld\n",x);
    }
    return 0;
}
#include<stdio.h>
#include<math.h>

int main()
{
    int n,t3,t2,i;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            double t=n*i;
            t2=sqrt(t*1.0);
            t3=t2*t2;
            if(t-t3<1e-8 && t-t3>-1e-8) break;
        }
        printf("%d\n",n+i+t2*2);
    }
    return 0;
}
#include <stdio.h>
#include <math.h>
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int i,t,y=1,m=n;
        for(i=2;n>1;i++){
            t=0;
            while(n%i==0){
                n/=i;
                t++;
            }
            if(t%2)
                y*=i;
        }
        printf("%d\n",m+y+2*(int)sqrt(m*y));
    }
    return 0;
}
#include <cstdio>
#include <cstring>
#include <cmath>
#define ll long long
struct eg
{
    int prime;
    int cnt;
}p[10010];
int main()
{
    int i,n,size;
    ll sum,m;
    while(scanf("%d",&n)!=EOF)
    {
        size=0;
        sum=1;
        m=n;
        for(i=2;i*i<=n;)
        {
            if(n%i==0)
            {
                p[size].prime=i;
                p[size].cnt=0;
                while(n%i==0)
                {
                    n/=i;
                    p[size].cnt++;
                }
                size++;
            }
            if(i==2) i++;
            else i+=2;
        }
        if(n>1) p[size].prime=n,p[size++].cnt=1;
        for(i=0;i<size;i++)
            if(p[i].cnt&1)
                sum*=p[i].prime;
        //printf("%lld\n",sum);
        ll ans=sum+m+2*(ll)sqrt(m*sum);
        printf("%lld\n",ans);
    }
    return 0;
}

D: Password(DP)

#include<stdio.h>
#include<string.h>
const int MOD=1234567;

int dp[1010];
char s[1010];

int main()
{
    int i,j,sum,T;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%s",s);
        int len=strlen(s);
        dp[0]=1;
        sum+=s[0]-'0';
        if(len>=1) dp[0]=1;
        if(len>=2)
        {
            sum=sum*10+s[1]-'0';
            if(sum>=10) dp[1]=dp[0]*2;
            else dp[1]=dp[0];
        }
        if(len>=3)
        {
            sum=(s[1]-'0')*10+(s[2]-'0');
            dp[2]=dp[1];
            if(sum>=10) dp[2]++;
            sum=sum+(s[0]-'0')*100;
            if(sum>=100 && sum<=255) dp[2]++;
        }
        for(i=3;i<len;i++)
        {
            sum=s[i]-'0';
            sum=sum+(s[i-1]-'0')*10;
            dp[i]=dp[i-1];//空
            if(sum>=10) dp[i]+=dp[i-2];//贴成两位数
            dp[i]%=MOD;
            sum=sum+(s[i-2]-'0')*100;
            if(sum>=100 && sum<=255) dp[i]+=dp[i-3];//贴成三位数
            dp[i]%=MOD;
        }
        printf("%d\n",dp[len-1]);
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation