JZSIM 3.2
空気浮遊
2019年03月02日
爆零大赛
WA CE 没写 三开花
T1 Pair
结论 + 构造一组合法方案
跟重心和贪心有关
然后某个循环的判断打错了（一个非运算（一个感叹号）） 100 -> 0
这已经不是我第一次犯这种错误了所以我认了... 不对这就是我第一次犯这种错误啊
为什么，为什么过了样例？为什么我没造样例？
nmd，wsm
// Code by ajcxsu
// Problem: pair
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void gn(T &x) {
char ch=getchar(), pl=0; x=0;
while(!isdigit(ch)) pl=(ch=='-'), ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }
const int N=1e5+10;
int h[N], to[N<<1], nexp[N<<1], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int con[N], siz[N], S, maxn, hvy;
int spe[N];
void dfs(int x, int fr) {
siz[x]=spe[x];
int ma=0;
for(int u=h[x];u;u=nexp[u])
if(to[u]!=fr) dfs(to[u], x), siz[x]+=siz[to[u]], ma=max(siz[to[u]], ma);
ma=max(ma, S-siz[x]);
if(ma<maxn) hvy=x, maxn=ma;
}
struct Stack {
int a[N];
int t=0;
int top() { return a[t]; }
void push(int x) { a[++t]=x; }
void pop() { t--; }
bool empty() { return !t; }
int size() { return t; }
} unfin, fin, deal, cac;
int tag[N], idx;
void add(int x, int fr) {
if(spe[x]) deal.push(x), tag[x]=idx;
for(int u=h[x];u;u=nexp[u])
if(to[u]!=fr) add(to[u], x);
}
void link(int a, int b) { con[a]=b, con[b]=a; }
void dfs2(int x) {
for(int u=h[x];u;u=nexp[u]) {
++idx;
add(to[u], x);
while(!unfin.empty() && !deal.empty()) {
link(deal.top(), unfin.top());
cac.push(unfin.top()), cac.push(deal.top()), deal.pop(), unfin.pop();
}
int nt=fin.t;
while(nt && deal.size()>=2) {
int v=con[fin.a[nt]];
if(tag[v]!=idx) {
link(fin.a[nt], deal.top()), cac.push(deal.top()), deal.pop();
link(v, deal.top()), cac.push(deal.top()), deal.pop();
}
nt--;
}
while(!deal.empty()) unfin.push(deal.top()), deal.pop();
while(!cac.empty()) fin.push(cac.top()), cac.pop();
}
if(!unfin.empty()) link(x, unfin.top());
}
int main() {
#ifndef LOCAL
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
#endif
int n, k;
gn(n, k);
int u, v, w;
for(int i=0; i<n-1; i++) gn(u, v, w), ins(u, v), ins(v, u);
for(int i=0; i<k; i++) gn(u), spe[u]=1;
dfs(1, 0), S=siz[1], maxn=0x3f3f3f3f, dfs(1, 0);
dfs2(hvy);
for(int i=1; i<=n; i++)
if(spe[i]) printf("%d %d\n", i, con[i]), spe[con[i]]=0;
return 0;
}T2 Rank
五年 OI 一场空...
为什么头文件要打 "hpp"？
为什么我没有想到可以排序 +cmp？
为什么我没有想到 cmp 可以只用一次 ask？
为什么我不知道有折半插入排序这种东西？
nmd，wsm
顺便，stable_sort 的比较次数竟然跟插入排序很接近...
可以发现根据复读人的类别变成这样：$AAA123BBB$，也就是分成五类人。
每次询问一对人，分四种情况讨论得到的询问组合，其中三种情况一定能分出至少一个人到 $A,B$，剩下一种情况是 $1,2,3$ 互相问。
然后对 $A,B$ 做插入排序即可。次数本地 10000 左右。
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include "rank.h"
namespace test
{
int n,rk[1234],qry=0;
}
char ask(int a,int b)
{
using namespace test; ++qry;
if(!(0<=a&&a<n&&0<=b&&b<n&&a!=b))
{
puts("invalid query!");
printf("%d %d\n",a,b);
exit(-1);
}
char s=(rk[a]<rk[b])?'b':'g';
if(rk[a]<1)
return (s=='g')?'n':s;
if(rk[a]==1) return 'n';
if(rk[a]==2)
return (rk[b]==3)?s:'n';
if(rk[a]==3)
return (s=='g')?'n':s;
return (s=='b')?'n':s;
}
int main()
{
freopen("rank.in","r",stdin);
using namespace test;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",rk+i);
std::vector<int> v=work(n);
if((int)v.size()!=n)
{
puts("wrong length");
exit(-1);
}
for(int i=0;i<n;++i)
if(v[i]!=rk[i])
{
puts("wrong answer");
exit(-1);
}
printf("Good job! You used %d queries.\n",qry);
}
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rint(int l, int r) { return rng()%(r-l+1)+l; }
const int N=1001, M=N*N;
vector<int> unc, A, B;
int rk[N], rel[N][N];
int h[N], to[M], nexp[M], in[N], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, in[b]++, p++; }
// 0 n 1 b 2 g
// meask(
inline int mea(int a, int b) {
if(a==b) return -1;
if(rel[a][b]!=-1) return rel[a][b];
char x=ask(a, b);
if(x=='n') return rel[a][b]=0;
if(x=='b') return rel[a][b]=1;
if(x=='g') return rel[a][b]=2;
return -1;
}
bool cmp(const int &a, const int &b) {
return !mea(a, b);
} // a<b
bool cmp2(const int &a, const int &b){
return mea(a, b);
}
vector<int> insert_sort(vector<int> arr, int a=-1, int b=-1) {
vector<int> res;
for(int x:arr)
if(x!=a && x!=b)
res.insert(lower_bound(res.begin(), res.end(), x, a==-1?cmp:cmp2), x);
return res;
}
vector<int> work(int n)
{
vector<int> ans;
memset(rel, -1, sizeof(rel));
for(int i=0; i<n; i++)
unc.push_back(i);
bool a[3];
int x, y, na, nb;
while(unc.size()>1) {
x=rint(0, unc.size()-1), y=rint(0, unc.size()-1);
if(x>y) swap(x, y);
na=unc[x], nb=unc[y];
if(unc.size()==2 && rel[na][nb]!=-1) break;
if(x==y || rel[na][nb]!=-1) continue;
a[0]=a[1]=a[2]=0;
int t1, t2;
a[t1=mea(na, nb)]=a[t2=mea(nb, na)]=1;
if(a[1] && a[0]) {
if(t1==1) A.push_back(na), unc.erase(unc.begin()+x);
else A.push_back(nb), unc.erase(unc.begin()+y);
}
else if(a[1] && a[2]) {
if(t1==1) A.push_back(na), B.push_back(nb);
else A.push_back(nb), B.push_back(na);
unc.erase(unc.begin()+y), unc.erase(unc.begin()+x);
}
else if(a[2] && a[0]) {
if(t1==2) B.push_back(na), unc.erase(unc.begin()+x);
else B.push_back(nb), unc.erase(unc.begin()+y);
}
}
int ham=-1;
if(unc.size()==2) {
na=unc[0], nb=unc[1];
for(int x:A) {
a[0]=a[1]=a[2]=0;
a[mea(na, x)]=a[mea(x, na)]=1;
if(a[0] && !a[1] && !a[2]) { ham=na, A.push_back(nb); break; }
}
if(ham==-1) ham=nb, A.push_back(na);
}
else ham=unc[0];
int sec=-1, thr=-1;
for(int x:A) {
a[0]=a[1]=a[2]=0;
a[mea(ham, x)]=a[mea(x, ham)]=1;
if(a[0] && !a[1] && !a[2]) {
if(sec==-1) sec=x;
else thr=x;
}
}
if(mea(sec, thr)!=1) swap(sec, thr);
B=insert_sort(B);
A=insert_sort(A, sec, thr);
// stable_sort(B.begin(), B.end(), cmp);
// stable_sort(A.begin(), A.end(), cmp);
int tot=3+B.size();
for(int j=B.size()-1;j>=0;j--) rk[B[j]]=tot--;
rk[thr]=tot--, rk[sec]=tot--, rk[ham]=tot--;
for(int j=A.size()-1;j>=0;j--) if(A[j]!=thr && A[j]!=sec) rk[A[j]]=tot--;
for(int i=0; i<n; i++) ans.push_back(rk[i]);
return ans;
}T3 Circuit
这题一开始让我想起了上次那道 bzoj 的那个焊画框的题目...
神仙构造...
就不赘述了题解讲得挺好的，都讲到位了...