好吧，做出來6題。。不想寫詳細的結題報告了，寫個簡略版的把
第一題，貪心，不用說
# include <cstdio>
using namespace std;
int main()
{
int test;
scanf("%d",&test);
for(int t=1;t<=test;t++)
{
int n;
long long c1,c2;
scanf("%d%I64d%I64d",&n,&c1,&c2);
long long last;
scanf("%I64d",&last);
long long total=2*c1+c2;
for(int i=1;i<n;i++)
{
long long tmp;
scanf("%I64d",&tmp);
if((tmp-last-1)*c2<2*c1)
total+=(tmp-last)*c2;
else
total+=c2+2*c1;
last=tmp;
}
printf("Case #%d: %I64d\n",t,total);
}
return 0;
} 第二題，BFS+位壓縮，也不用說
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int n;
char str[2][20];
int len[1<<20];
queue<int> q;
inline bool getbit(int code,int n)
{
return code&(1<<n);
}
int change(int code,int h1,int w1,int h2,int w2,char color)
{
for(int i=h1;i<h2;i++)
for(int j=w1;j<w2;j++)
if(str[i][j]==color)
code|=(1<<(2*j+i));
else if(getbit(code,2*j+i))
code-=(1<<(2*j+i));
return code;
}
void print(int code)
{
printf("\n");
for(int i=0;i<n;i++)
printf("%d ",getbit(code,2*i));
printf("\n");
for(int i=0;i<n;i++)
printf("%d ",getbit(code,2*i+1));
printf("\n");
}
int main()
{
int test;
scanf("%d",&test);
for(int t=1;t<=test;t++)
{
scanf("%d%s%s",&n,str[0],str[1]);
memset(len,-1,sizeof(len));
while(!q.empty())
q.pop();
len[0]=0;
q.push(0);
int target=(1<<(2*n))-1;
while(!q.empty())
{
int top=q.front();
q.pop();
//print(top);
if(top==target) break;
for(int i=0;i<n;i++)
{
if(!getbit(top,2*i))
{
for(int w=1;w<=n-i;w++)
{
int newcode=change(top,0,i,1,i+w,str[0][i]);
if(len[newcode]==-1)
len[newcode]=len[top]+1,q.push(newcode);
newcode=change(top,0,i,2,i+w,str[0][i]);
if(len[newcode]==-1)
len[newcode]=len[top]+1,q.push(newcode);
}
}
if(!getbit(top,2*i+1))
{
for(int w=1;w<=n-i;w++)
{
int newcode=change(top,0,i,2,i+w,str[1][i]);
if(len[newcode]==-1)
len[newcode]=len[top]+1,q.push(newcode);
newcode=change(top,1,i,2,i+w,str[1][i]);
if(len[newcode]==-1)
len[newcode]=len[top]+1,q.push(newcode);
}
}
}
}
printf("Case #%d: %d\n",t,len[target]);
}
return 0;
}第三題，想暴力+hash+樹最小表示，悲劇的TLE，估計用stl效率太低了
賽后我用java寫出來了，1A
1 import java.io.*;
2 import java.util.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static int leg[]=new int[1<<15],p;
9 static HashSet<String> refer[]=new HashSet[1<<15];
10 static int g[]=new int[15],v[]=new int[50],nxt[]=new int[50],c,n;
11 static boolean used[]=new boolean[15];
12 static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
13 static int input() throws IOException
14 {
15 in.nextToken();
16 return (int)in.nval;
17 }
18 static void insert(int a,int b)
19 {
20 v[c]=b;
21 nxt[c]=g[a];
22 g[a]=c++;
23 v[c]=a;
24 nxt[c]=g[b];
25 g[b]=c++;
26 }
27 static boolean getbit(int bit,int pos)
28 {
29 return (bit&(1<<pos))!=0;
30 }
31 static void chk(int now,int pre,int code)
32 {
33 used[now]=true;
34 for(int i=g[now];i!=-1;i=nxt[i])
35 if(v[i]!=pre&&getbit(code,v[i]))
36 chk(v[i],now,code);
37
38 }
39 static boolean chk(int now,int code)
40 {
41 Arrays.fill(used,false);
42 chk(now,now,code);
43 for(int i=0;i<n;i++)
44 if(getbit(code,i))
45 if(!used[i])
46 return false;
47 return true;
48 }
49 static String dfs(int now,int pre,int code)
50 {
51 ArrayList<String> tmp=new ArrayList<String>();
52 for(int i=g[now];i!=-1;i=nxt[i])
53 if(v[i]!=pre&&getbit(code,v[i]))
54 tmp.add(dfs(v[i],now,code));
55 Collections.sort(tmp);
56 StringBuffer ans=new StringBuffer("(");
57 for(String i:tmp)
58 ans.append(i);
59 ans.append(")");
60 return ans.toString();
61 }
62 public static void main(String[] args) throws IOException{
63 int test=input();
64 for(int i=0;i<(1<<15);i++)
65 refer[i]=new HashSet<String>();
66 for(int t =1;t<=test;t++)
67 {
68 p=0;
69 c=0;
70 Arrays.fill(g,-1);
71 n=input();
72 for(int i=1;i<n;i++)
73 insert(input()-1,input()-1);
74 for(int i=1;i<(1<<n);i++)
75 {
76 int start=-1;
77 for(int j=0;j<n&&start==-1;j++)
78 if(getbit(i,j))
79 start=j;
80 if(!chk(start,i)) continue;
81 leg[p++]=i;
82 refer[i].clear();
83 for(int j=start;j<n;j++)
84 if(getbit(i,j))
85 refer[i].add(dfs(j,j,i));
86 }
87 int total=0;
88 for(int i=0;i<p;i++)
89 {
90 boolean flag=true;
91 for(String ii:refer[leg[i]])
92 {
93 for(int j=0;j<i&&flag;j++)
94 if(refer[leg[j]].contains(ii))
95 flag=false;
96 if(!flag) break;
97 }
98 if(flag) total++;
99 }
100 System.out.println("Case #"+t+": "+total);
101 }
102
103 }
104
105 }
第四題：不知道
第五題：我女友寫的~恩，也是我們隊數學最牛的~，思想不明。。
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int m,t,k;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
//cin>>m>>k;
scanf("%d%d",&m,&k);
printf("Case #%d: ",i);
printf("%.8f\n",1.0/(m*k+k+1));
//cout<<endl;
}
}
第六、七題：不知道
第八題：簡單字符串處理，MS上次復旦邀請賽也有這么一道關于URL的題目
include <cstdio>
# include <cstdlib>
# include <cstring>
using namespace std;
char str[1024];
int main()
{
int test;
scanf("%d",&test);
getchar();
for(int t=1;t<=test;t++)
{
gets(str);
int begin;
for(begin=0;str[begin]!=':';begin++);
begin+=3;
for(int i=begin;str[i]!='\0';i++)
if(str[i]==':'||str[i]=='/')
{
str[i]='\0';
break;
}
printf("Case #%d: %s\n",t,str+begin);
//puts(str+begin);
}
return 0;
}
第十題：數據結構的聯合，首先大數組以人編號為第一關鍵字，click為第二關鍵字排序，用圖中類似前向星的結構來存儲第幾個人的開始位置。然后就是掃描，這里一定要用鏈表，復雜度O(m)，不然復雜度會高達o(mn)，然后肯定TLE。話說。開始我用vector想省事，結果RE了。。復旦數據卡的太大了
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <list>
using namespace std;
# define M 500005
# define N 100005
struct node
{
int id,click,length;
bool operator<(const node &pos) const
{
if(id!=pos.id) return id<pos.id;
else return click>pos.click;
}
}data[M];
int n,m,q;
int s[N];
long long ans[M];
list<int> li;
int main()
{
int test;
scanf("%d",&test);
for(int t=1;t<=test;t++)
{
scanf("%d%d%d",&n,&m,&q);
for(int i=0;i<m;i++)
scanf("%d%d%d",&data[i].id,&data[i].click,&data[i].length);
sort(data,data+m);
memset(s,-1,sizeof(s));
for(int i=0;i<m;i++)
if(s[data[i].id]==-1)
s[data[i].id]=i;
int now=1;
ans[0]=0;
li.clear();
for(int i=1;i<=n;i++)
if(s[i]!=-1) li.push_back(i);
while(!li.empty())
{
ans[now]=ans[now-1];
for(list<int>::iterator i=li.begin();i!=li.end();)
{
ans[now]+=data[s[*i]].length;
s[*i]++;
if(s[*i]>=m||data[s[*i]].id!=data[s[*i]-1].id)
i=li.erase(i);
else i++;
}
now++;
}
printf("Case #%d:\n",t);
while(q--)
{
int num;
scanf("%d",&num);
if(num>=now) num=now-1;
printf("%I64d\n",ans[num]);
}
}
return 0;
}