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;
}
[……]
继续阅读