Codeforces Round #343 (Div. 2 Only)
感谢JCarlson和quailty翻译
最终Rank 51,做题情况:
My Submissions
My contest submissions
E给弄伤了
A
给你个矩阵(由'.'和'C'组成),求有多少对'C'同一行或者同一列
直接暴力即可..
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[105][105];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
scanf("%s",a[i]);
}
int ans=0;
for (i=0;i<n;i++)
{
int j;
int sum=0;
for (j=0;j<n;j++)
{
if (a[i][j]=='C') sum++;
}
ans+=sum*(sum-1)/2;
}
for (i=0;i<n;i++)
{
int j;
int sum=0;
for (j=0;j<n;j++)
{
if (a[j][i]=='C') sum++;
}
ans+=sum*(sum-1)/2;
}
printf("%d\n",ans);
return 0;
}
B:
你有N个朋友,有的是男的有的是女的
现在你要在某一天开个party,你需要请的男的和女的数目一样多
某人在第xi到yi天有空来party
求最多多少人参加party
直接暴力一下就好了吧...对于MedalPlus的查分约束...我不好说...
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[505],b[505];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
char x;
cin>>x;
int y,z;
scanf("%d%d",&y,&z);
int j;
for (j=y;j<=z;j++)
{
if (x=='F') a[j]++; else b[j]++;
}
}
int ans=0;
for (i=0;i<=400;i++)
{
ans=max(ans,min(a[i],b[i]));
}
printf("%d\n",ans*2);
return 0;
}
D:
给你n个蛋糕,每个蛋糕有ri和hi(它的体积是ri*ri*hi)
每个蛋糕只能放在编号比自己小,而且体积也比自己小的蛋糕上
求最大能放多少体积蛋糕
是个dp,但会导致n^2会TLE
所以我写了个线段树优化...似乎有点多此一举?
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
long long val[1<<18];
const double pi=3.1415926535897932384626433832795;
long long h[100005];
void change(int num,int l,int r,int k,long long t)
{
if (l==r-1)
{
val[num]=max(val[num],t);
return;
}
int mid=(l+r)/2;
if (k<mid)
{
change(num*2+1,l,mid,k,t);
}
else
{
change(num*2+2,mid,r,k,t);
}
val[num]=max(val[num*2+1],val[num*2+2]);
}
long long query(int num,int l,int r,int l0,int r0)
{
if ((l0<=l)&&(r<=r0))
{
return val[num];
}
long long ans=0;
int mid=(l+r)/2;
if (l0<mid) ans=max(ans,query(num*2+1,l,mid,l0,r0));
if (mid<r0) ans=max(ans,query(num*2+2,mid,r,l0,r0));
return ans;
}
map<long long,int> ma;
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
int x;
scanf("%d",&x);
h[i]=x*x;
scanf("%d",&x);
h[i]*=x;
ma[h[i]]=0;
}
map<long long,int>::iterator ii;
int sum=0;
for (ii=ma.begin();ii!=ma.end();ii++)
{
(*ii).second=sum++;
}
for (i=0;i<n;i++)
{
long long ans=h[i];
ans+=query(0,0,sum,0,ma[h[i]]);
change(0,0,sum,ma[h[i]],ans);
}
printf("%.12lf\n",query(0,0,sum,0,sum)*pi);
return 0;
}
C:
给你个长度为m的括号序列
在前面后面加若干括号,使得它合法且长度为n
求有多少种不同方案(注意:即使最终结果相同,加在前面的东西或者后面的东西不同也是一种方案,如样例一个左括号:
In the first sample there are four different valid pairs:
- p = "(", q = "))"
- p = "()", q = ")"
- p = "", q = "())"
- p = "", q = ")()"
1和2都是"(())",但算不同方案
n,m<=1e5,但是n-m<=2000
所以我写了个dp
dp(i,j,0)表示在前面放了i个括号,目前左括号比右括号多j个
dp(i,j,1)则表示已经放到右边去了,用了i个括号左比右多j
加一点特判,也能过
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[100005];
const int modo=1000000007;
int dp[2005][2005][2];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",a);
int i;
int sum=0;
int min=0;
for (i=0;i<m;i++)
{
if (a[i]=='(') sum++; else sum--;
if (sum<min) min=sum;
}
if (sum>2000)
{
puts("0");
return 0;
}
if (sum<-2000)
{
puts("0");
return 0;
}
n-=m;
// ((((( .... ( ()()()() .... () )))) .... )
// -min n pairs (n*2) sum-min
dp[0][0][0]=1;
int j,k;
for (i=0;i<=n;i++)
{
for (j=-min;j<=2000;j++)
{
if (j+sum>2000) continue;
dp[i][j+sum][1]+=dp[i][j][0];
dp[i][j+sum][1]%=modo;
}
for (j=0;j<=2000;j++)
{
if (j!=0)
{
dp[i+1][j-1][0]+=dp[i][j][0];
dp[i+1][j-1][0]%=modo;
dp[i+1][j-1][1]+=dp[i][j][1];
dp[i+1][j-1][1]%=modo;
}
if (j!=2000)
{
dp[i+1][j+1][0]+=dp[i][j][0];
dp[i+1][j+1][0]%=modo;
dp[i+1][j+1][1]+=dp[i][j][1];
dp[i+1][j+1][1]%=modo;
}
}
}
printf("%d\n",dp[n][0][1]);
return 0;
}
E:
给你n个点的树
给你m对点x和点y
求任意加一条边,使得x和y连出环的情况下(即有两条路径能从x到y,不一定x到y一定有一条边,可以绕一段),环的期望长度
可以将这棵树拆开,拆成三部分
x为根的子树
y为根的子树
x--y之间的路径,以及上面带的叶子
考虑随意瞎选,一定在第一部分和第二部分各选中一次,才会导致x,y连出一个环
那么只要求在x为根子树瞎选一个到x的平均距离即可,加到答案上
再在y为根求一边,最后求两点之间的距离+1
答案加起来即可
x为根的子树瞎选一个到x的平均距离可以通过dfs两次来求出所有点为根的总深度和
每次只要去掉y所在的子树的深度和即可
代码如下:(中间试数据WA/RE了好多次)(竟然二分试哪个询问RE了2333)
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct edge
{
int y;
edge * next;
};
edge * li[100005];
edge * new_edge()
{
static edge a[200005];
static int top=0;
return &a[top++];
}
void inserts(int x,int y)
{
edge * t=new_edge();
t->y=y;
t->next=li[x];
li[x]=t;
}
void insert_edge(int x,int y)
{
inserts(x,y);
inserts(y,x);
}
int size[100005];
long long sum_depth[100005];
long long up_depth[100005];
int depth[100005];
int up[100005][25];
void dfs1(int x)
{
size[x]=1;
edge * t;
for (t=li[x];t!=0;t=t->next)
{
if (size[t->y]==0)
{
depth[t->y]=depth[x]+1;
up[t->y][0]=x;
dfs1(t->y);
size[x]+=size[t->y];
sum_depth[x]+=sum_depth[t->y];
sum_depth[x]+=size[t->y];
}
}
}
int n;
void dfs2(int x,long long y)
{
up_depth[x]=y;
edge * t;
for (t=li[x];t!=0;t=t->next)
{
if (up_depth[t->y]==-1)
{
dfs2(t->y,up_depth[x]+sum_depth[x]-sum_depth[t->y]-size[t->y]+(n-size[t->y]));
}
}
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int m;
scanf("%d%d",&n,&m);
int i;
int kkk=n+m;
for (i=0;i<n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if (i==0) kkk+=x;
x--;
y--;
insert_edge(x,y);
}
depth[0]=0;
dfs1(0);
memset(up_depth,-1,sizeof(up_depth));
dfs2(0,0);
up[0][0]=-1;
int j;
for (j=1;j<=20;j++)
{
for (i=0;i<n;i++)
{
if (up[i][j-1]==-1)
{
up[i][j]=-1;
}
else
{
up[i][j]=up[up[i][j-1]][j-1];
}
}
}
for (i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x--;
y--;
if (depth[x]<depth[y]) swap(x,y);
int xx=x;
int t=depth[x]-depth[y]-1;
if (t==-1) t=0;
int j;
for (j=0;j<20;j++)
{
if (t&(1<<j))
{
x=up[x][j];
}
}
long long ans_x=sum_depth[xx];
int size_x=size[xx];
long long ans_y;
int size_y;
int road=depth[xx]-depth[y];
if (up[x][0]==y)
{
ans_y=sum_depth[y]+up_depth[y]-sum_depth[x]-size[x];
size_y=n-size[x];
}
else
{
int flag=0;
ans_y=sum_depth[y];
size_y=size[y];
if (depth[x]==depth[y]+1) x=up[x][0];
int i;
for (i=20;i>=0;i--)
{
if (up[x][i]==up[y][i]) continue;
x=up[x][i];
y=up[y][i];
road+=(1<<i);
road+=(1<<i);
}
road+=2;
}
printf("%.12lf\n",1.0*ans_x/size_x+1.0*ans_y/size_y+road+1);
}
return 0;
}
Feb 23, 2016 08:34:15 PM
您太神啦
Feb 24, 2016 12:19:25 PM
WA/RE/CE一共39次也是累死了....
Feb 24, 2016 12:20:03 PM
哦不是43次....外加一次AC一共44次提交,换做ACM赛制估计早就23333了