## The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup 个人题解

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

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

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

}```

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

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

posted on 2011-09-07 22:30 yzhw 阅读(575) 评论(2)  编辑 收藏 引用 所属分类: others

### 评论

#### #re: The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup 个人题解 2011-09-08 12:10 yzhw

@tjt

 只有注册用户登录后才能发表评论。 【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！ 相关文章:
 < 2011年9月 >
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

• 随笔 - 183
• 文章 - 2
• 评论 - 27
• 引用 - 0

•

• 积分 - 49445
• 排名 - 449