A
啥都不說了,,,秒
話說我把abcd打錯了WA了一發
#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了
雖然我手速慢,但,,,,這顯然是以前做過啊
#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值就是其父親的編號
#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),配合一個簡單的二分查找
#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;
}
codeforces排名、調試的時候為了編譯快一點,把MAXN調的很小,然后瘋狂RTE
自己盯著代碼看了半天,,
誒,還是要細心啊
E題,,,大坑待填