Category Archives: 解题报告

[转]某大牛的工作总结

刚刚结束了在度厂一年的实习，终于进入了期待已久的休假期，接下来集中写写毕设论文，准备一下答辩的事宜。

 

在这里扯一点淡，也算是纪念一下被狗吃了的青春，另一方面也是希望能够对同样正在经历之前这些阶段的人有一些帮助吧。这些可能对各方面比较普通的同学有一些帮助，各种牛逼大神请自动忽[……]

继续阅读

并查集(附:SDIBT_12级暑假集训第五天—A题解)

做并查集时有三个步骤，即:初始化(makeset)——>查找根(findset)——>合并集合(union)。只要掌握了这三步，一些简单的并查集也就差不多OK了。
一、初始化:
官方点的话说就是把每个点所在的集合初始化为其自身。
这个不难，就直接把代码贴上：
void makes[……]

继续阅读

Area(Pick定理应用)

经过一天在网上搜各种资料，马马虎虎总结了套模板，虽然个别地方不太理解，这个模板也是比较大众化的。

核心公式就是Pick定理：S=内点个数+边上点个数/2-1；

难点也就在于计算点的个数；

思路是先求最好求的边上点的个数，就是对每组x，y的绝对值求最大公约数加和可得；

然后就是[……]

继续阅读

新秀A~B

A：To save the princess

找规律题（霞娘指点）。先求行与列的最大公约数，说白了就是把行和列约分化简。之后很容易得到规律：行+列-1。。

代码：

#include<stdio.h>
int gy(int a,int b)
{
int t;
if[……]

继续阅读

2013sdibt校赛（A-H）

A

a题看的时候就想，要是没有交点就简单了，没交点的话必然是（m+n-1）。那怎么把有交点的化成没交点的呢？分成全等的就好了嘛。所以，最大公约数求一下。然后，这题没什么要注意的细节，1A就是了。

B

开始看是英文就跳过去了，后来发现好多人都A了，无奈英语坑去看了，开始想各种办法去模[……]

继续阅读

12级集训队训练赛（六）B – 数学谜题 （解析）

这道题是POJ1063，这里找了一篇解释详细的报告：

题意:给定一个数N (10 <=N <= 30),然后给你N个数,这N个数由0和1组成,这N个数可以看做是一个环.然后现在又一种操作,可以将连续的三个数进行翻转,也可以将整个序列顺时针旋 转一圈.现在问是否存在通过一个操作来是的[……]

继续阅读

Wooden Sticks

Description

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a w[……]

继续阅读

E – A so easy question

这题感觉没什么好说的,考的思维,看出规律模拟即可。。不过发现dfy的代码写的比我好多了~~就把她的贴上来吧。

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int t,x,y,i,j,a[100][......]
继续阅读

D – 简单的加减法（解题思路）

这道题是改编题，原题是：http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=394#problem/E

网上关于此题的代码和解释非常多，各种思路，我就不解释了，下面是我的做法，供参考～

#include <stdio.h[......]
继续阅读

Problem A

分析：
在计算机上进行高精度计算，首先要处理好以下几个基本问题：
1、数据的接收与存储；
2、计算结果位数的确定；
3、进位处理和借位处理；
4、商和余数的求法；

输入和存储
运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。能表示多个数的数据类型有两种：数组[……]

继续阅读

Warmup 2 for the 7th BUPT Programming Contest

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;
}

[……]

继续阅读

zoj2723（1172Semi-Prime）

先筛选求素数了，存下500000内的素数然后打表把1000000内的半素数都求出来了。巨麻烦。求简单解法。

#include <stdlib.h>
#include <stdio.h>
int p[2000000]={0},cp[500005]={1,1},sp[1[……]

继续阅读