【题解】GoogleCodeJam2021-QualificationRound
⼯作好久，回来打⼀场程序设计⽐赛真是神清⽓爽。
顺便配好了 sublime 的插件 以及 Terminus，前者可以⽅便地输⼊样例执⾏等，后者则是⼀个内置命令⾏，效率提升不少。
A. Reversort
按字⾯意思模拟即可。
#include<iostream>
#include<algorithm>
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main(){
int T =read();
for(int kase=1; kase<=T;++kase){
int n =read(), L[128];
for(int i=1; i<=n;++i){
L[i]=read();
}
int ans =0;
for(int i=1; i<n;++i){
int j = std::min_element(L+i, L+n+1)-L;
std::reverse(L+i, L+j+1);
ans += j-i+1;
}
printf("Case #%d: %d\n", kase, ans);
}
}
B Moons and Umbrellas
简单的动态规划，dp[i] 表⽰ i 位置选 C/J，之前全部确定的最⼩代价.
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char S[1024];
int dp[1024][2];// dp[i] 表⽰ i 位置选 C/J，之前全部确定的最⼩代价
bool valid[1024][2];// valied[i] 表⽰ i 位置选 C/J 是否合法
inline int valid_min(int a,int b,bool va,bool vb){
if(va && vb)return std::min(a, b);
if(va)return a;
return b;
}
int main(){
int T =read();
for(int kase=1; kase<=T;++kase){
int x=read(), y=read();
scanf("%s", S);
for(int i=0; S[i];++i){
valid[i][0]= valid[i][1]=1;
if(S[i]=='C') valid[i][1]=0;// can't be J
if(S[i]=='J') valid[i][0]=0;
}
dp[0][0]= dp[0][1]=0;
for(int i=1; S[i];++i){
dp[i][0]=valid_min(dp[i-1][0], dp[i-1][1]+ y, valid[i-1][0], valid[i-1][1]);
dp[i][1]=valid_min(dp[i-1][1], dp[i-1][0]+ x, valid[i-1][1], valid[i-1][0]);
}
int n =strlen(S);
int ans =valid_min(dp[n-1][0], dp[n-1][1], valid[n-1][0], valid[n-1][1]);
printf("Case #%d: %d\n", kase, ans);
}
}
C. Reversort Engineering
下⾯的思路是做题的时候写在注释⾥的，直接 copy 出来 hhh：
到⼀个长为 N 的排列，使得 reverseSort 所花费的代价恰好为 C
N <= 100, C <= 1000
注意到 reverseSort 过程中和数字绝对⼤⼩⽆关，只和相对⼤⼩有关，考虑递归缩⼩问题规模。
记 P(N,C) 为⼀个长为 N，reverseSort 代价为 C 的排列，即所求答案。
如果已经有 P(N-1, C-1)， 想要得到 P(N, C)，只需要在最前⾯添加⼀个更⼩的数字即可。
如果有 P(N-1, C-2)，想要得到 P(N, C)，需要把更⼩的数字插⼊到第⼀个元素后⾯。
如果有 P(N-1, C-3)，想要得到 P(N, C)，需要把前两个元素翻转，然后把更⼩的数字插⼊到第 2 个元素后⾯。
如果有 P(N-1, C-x)，想要得到 P(N, C)，需要把前 x-1 个元素翻转，然后把更⼩的数字插⼊到第 x-1 个元素后⾯，作为第 x 个元素
x 的取值范围 【1，N】
对于长为 N 的排列，最⼩的 C 是 N-1, 最⼤的 C 是 sum(2 … N)，显然其中的每个值都可以取到。
换句话说，问题的本质相当于构造⼀个长为 N 的数组，第⼀个元素固定为 0，第 i 个元素最⼩值为 1，最⼤值为 i，使得它们的和等于 C 等价于，构造⼀个长为 N 的数组，第 i 个元素的最⼩值为 0, 最⼤值为 i-1，使它们的和等于 C-(N-1)
得到了这个差值数组之后，想要构建出 P(N,C) 怎么办呢，按上⾯的⽅法构造即可。
vector::insert(pos, t) 可以把 t 插⼊到 pos 迭代器指向的元素之前
#include<algorithm>
#include<vector>
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main(){
int T =read();
for(int kase=1; kase<=T;++kase){
int N=read(), C=read();
if(C < N-1|| C > N*(N+1)/2-1){
printf("Case #%d: IMPOSSIBLE\n", kase);
continue;
}
std::vector<int>resident(N+1);//差值数组
resident[1]=0;
for(int i=2, tc=C-(N-1); i<=N;++i){
resident[i]= std::min(i-1, tc);
tc -= resident[i];
++resident[i];
}
std::vector<int>ans(2, N);
for(int i=2; i<=N;++i){
reverse(ans.begin()+1, ans.begin()+resident[i]);
ans.insert(ans.begin()+resident[i], N-i+1);
}
printf("Case #%d:", kase);
for(int i=1; i<=N;++i){
printf(" %d", ans[i]);
}
printf("\n");
}
}
D. Median Sort
给⼀个长为 N=50 的数组，可以询问 Q=170 次 midian, 然后给出顺序。 交互题。
维护当前排好序的元素，每次通过三分查确定新元素的位置，可以证明最坏情况只需要 160 次询问。三分的具体细节见注释
#include<iostream>
#include<algorithm>
#include<vector>
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int query(int a,int b,int c){
printf("%d %d %d\n", a, b, c);
fflush(stdout);
int res =read();
if(res==-1){
exit(0);
}
}
return res;
}
int answer(std::vector<int>&ans){
for(auto x: ans){
printf("%d ",x);
}
printf("\n");
fflush(stdout);
int res =read();
if(res==-1){
exit(0);
}
return res;
}
/*
vector::insert(pos, t) 把 t 插⼊到 pos 位置指向的元素之前
在 [a, b) 范围内到第⼀个迭代器，它是第⼀个⼤于 t 的元素，如果没有，就是 b.
⼀共有 b-a+1 个位置可以插⼊，尽可能均匀地分成三份
边界情况：
a=b, 没有元素了，⼀个插⼊位置，直接插⼊到 a 处
a+1=b，还剩⼀个元素，两个插⼊位置，不要处理这种情况，出现时扩张⼀位
a+2=b，还剩两个元素，三个插⼊位置，会使⽤ *a, *(a+1), id 进⾏⼀次⽐较，然后分割成 {a,a}, {a+1,a+1}, {a+2, a+2} 三种情况a+3=b，还剩三个元素，四个插⼊位置，会使⽤ *(a+1), *(a+2), id 使⽤⼀次⽐较，然后分割成 {a,a+1}, {a+2, a+2}, {a+3, a+3}通⽤分割⽅式：m1 = a+(b-a)/3, m2 = a+(b-a)*2/3，分割范围：{a, m1}, {m1+1, m2}, {m2+1, b}
*/
std::vector<int> ans;
using IT = std::vector<int>::iterator;
IT ternary_search(IT a, IT b,int id){
if(a>=b)return a;
if(a+1==b){
if(a==ans.begin()){
return ternary_search(a, b+1, id);
}else{
return ternary_search(a-1, b, id);
}
}
IT m1 = a+(b-a)/3, m2 = a+(b-a)*2/3;
int res =query(*m1,*m2, id);
if(res ==*m1)return ternary_search(a, m1, id);
if(res == id)return ternary_search(m1+1, m2, id);
/*if(res == *m2)*/return ternary_search(m2+1, b, id);
}
int main(){
int T=read(), N=read();read();
while(T--){
int res =query(1,2,3);
if(res==1) ans = std::vector<int>{2,1,3};
if(res==2) ans = std::vector<int>{1,2,3};
if(res==3) ans = std::vector<int>{1,3,2};
for(int i=4; i<=N;++i){
auto it =ternary_search(ans.begin(), d(), i);
ans.insert(it, i);
}
answer(ans);
}
}
E. Cheating Detection
100个玩家，10000道题，各有⼀个 level。正常玩家做题正确的概率是 sigmoid(level_player - level_question)，有⼀个作弊者，它有⼆分之⼀的概率⼀定做对，剩下的情况⾛正常概率。
所有 level 和结果随机⽣成，给定做题结果，出作弊者，要求成功率达到 86%.
1. ⾸先把题⽬按做出⼈数排序，把玩家按做出题⽬数排序，然后随机出若⼲个 level 按顺序分配给他们。
2. 然后将题⽬按难度分成100块，每块100道题，计算出每个玩家做每块题⽬的期望正确数与实际正确数，放到⼀个怀疑函数⾥⾯计算
怀疑值。
3. 输出怀疑值最⾼的玩家。
提⾼成功率的⽅法：只看最难的那些题，或者给怀疑函数加上⼀个权重系数，越难的题权重越⼤，因为正常⼈做最难的题的成功概率不会超过 50%，⽽作弊者的频率⼀定会超过50%.
cstring转为int本地测试，我的成功率是 89%，提交也 AC 了。感觉还有很多可以改进的点，⽐如按实际做出来的题⽬数拟合玩家的 level，⽽不是按随机值分配。
推荐本地⽣成⼀组数据⽤于测试。
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
constexpr int P =100, Q =10000;
char save[128][10016];
struct Item {
int id;// id
int cnt;// 计数
double level;// 等级
double suspicion;//怀疑度
bool operator<(const Item &b)const{
return cnt<bt;
}
};
Item players[128], questions[10016];
double rnd1[128], rnd2[10016];
inline double randD(){
return(double)rand()/RAND_MAX*6-3;
}
double sigmoid(double x){
return1.0/(1.0+exp(-x));
}
void rand_init(){
srand(114514);
for(int i=1; i<=P;++i) rnd1[i]=randD();
for(int i=1; i<=Q;++i) rnd2[i]=randD();
std::sort(rnd1+1, rnd1+P+1);
std::sort(rnd2+1, rnd2+Q+1);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。