8.7排位赛,codeforces501

Posted by Cww97 on 2016-08-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52145256
A
啥都不说了,,,秒
话说我把abcd打错了WA了一发这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<algorithm>
using namespace std;
int get(int p,int t){
return max(3*p/10,p-p/250*t);
}

int main(){
int a,b,c,d;
while (scanf("%d%d%d%d",&a,&b,&c,&d)==4){
int m=get(a,c);
int v=get(b,d);
if (m==v)puts("Tie");
else if (m>v)puts("Misha");
else puts("Vasya");
}
return 0;
}

B,,,
不多说,还是秒
话说在提交A 的时候就看到有人交B了
虽然我手速慢,但,,,,这显然是以前做过啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
const int N=1007;
string Old[N],New[N];
int n,q;

int Find(string st){
for (int i=1;i<=n;i++){
if (New[i]==st)return i;
}
return -1;
}

int main(){
//freopen("fuck.in","r",stdin);
string st,stt;
cin>>q;
while (q--){
cin>>st>>stt;
int pos=Find(st);
if (pos!=-1)New[pos]=stt;
else{
Old[++n]=st;
New[ n]=stt;
}
}
printf("%d\n",n);
for (int i=1;i<=n;i++){
cout<<Old[i]<<" "<<New[i]<<endl;
}
return 0;
}

C
题意说啥无环,,就是个树了
啊呸,森林(题目都说了)
弄个队列或者dfs都行吧,从叶子节点向上删边
显然叶子几点的sum值就是其父亲的编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=100007;
struct Edge{
int from,to;
Edge(){}
Edge(int x,int y){from=x,to=y;}
}edges[N];
int n,d[N],s[N];

int main(){
//freopen("fuck.in","r",stdin);
scanf("%d",&n);
queue<int>Q;
for (int i=0;i<n;i++){
scanf("%d%d",&d[i],&s[i]);
if (d[i]==1)Q.push(i);
}
int m=0;
while (!Q.empty()){
int k = Q.front();Q.pop();
if (d[k]==0)continue;
edges[++m]=Edge(k,s[k]);
d[s[k]]--;
s[s[k]] ^= k;
if (d[s[k]]==1)Q.push(s[k]);
}
printf("%d\n",m);
for (int i=1;i<=m;i++){
printf("%d %d\n",edges[i].from,edges[i].to);
}
return 0;
}

D,
这个,,,学术一点,叫康托展开和康托逆展开
其实就是求第几个排列和求这个排列是第几个排列
n有20W,阶乘肯定爆炸,用多项式存,每位是k!,这项达到k+1的时候就进位
反正康托展开的赤裸裸的形式也是除法取模之类的,,,这样正好直接把没项值搞出来了

数据量略大,读入的时候用树状数组或者线段树维护一下逆序对
处理的时候还是用树状数组求第k大数(注意+1,树状数组是1~n),配合一个简单的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200020;
int n,c[N],a[N],fac[N];

void add(int k){
for (;k<=n;k+=k&(-k)){c[k]++;}
}
int sum(int k){
int s=0;
for (;k;k-=k&(-k)){s+=c[k];}
return s;
}

void order(){
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
for (int i=n;i>=1;i--){
fac[n-i]+=sum(a[i]+1);
add(a[i]+1);
}
}

int get(int k){
int l = k,r = n;
while (l < r){
int mid = (l+r)>>1;
if (mid-sum(mid)<k) l=mid+1;
else r=mid;
}
add(l);
return l-1;
}

int main(){
//freopen("fuck.in","r",stdin);
scanf("%d",&n);
order();order();
for (int i=0;i<n;i++){
fac[i+1]+=fac[i]/(i+1);
fac[i] %= (i+1);
}

memset(c,0,sizeof(c));
for (int i=1;i<=n;i++) a[i]=get(fac[n-i]+1);
for (int i=1;i< n;i++) printf("%d ",a[i]);
printf("%d\n",a[n]);
return 0;
}

调试的时候为了编译快一点,把MAXN调的很小,然后疯狂RTE
自己盯着代码看了半天,,
诶,还是要细心啊
这里写图片描述

E题,,,大坑待填