HDK 在与 mt19937_64 先生的石头剪刀布比赛中拿下十一连败的好成绩
你也来试试吧
#include<bits/stdc++.h>
using namespace std;
#include"include/hdk/rand.h"
using namespace hdk::Rand;
char getchar_(){char ch=getchar();if(ch>='a' and ch<='z') ch+=('A'-'a');while(ch!='S' and ch!='R' and ch!='P'){ch=getchar();if(ch>='a' and ch<='z') ch+=('A'-'a');}return ch;
}
int cnt=0,tot=0,totm=0;
int main(){randt.device_srand();while(1){totm++;cout<<"Act (R 石头 | S 剪刀 | P 布)>>";cout.flush();char ans=getchar_();char act=randt.randfrom<char>({'R','S','P'});cout<<"Robot act with "<<act<<endl;if(ans==act){cout<<"Draw."<<endl;}else if(ans=='R'){if(act=='S'){cout<<"You win."<<endl;tot++;cnt++;}if(act=='P'){cout<<"You lost."<<endl;cnt=0;}}else if(ans=='S'){if(act=='R'){cout<<"You lost."<<endl;cnt=0;}if(act=='P'){cout<<"You win."<<endl;tot++;cnt++;}}else{if(act=='R'){cout<<"You win."<<endl;tot++;cnt++;}if(act=='S'){cout<<"You lost."<<endl;cnt=0;}}cout<<"Longest Streak: "<<cnt<<" Rounds"<<endl;cout<<"Win: "<<tot<<"/"<<totm<<endl<<endl;}
}
rand.h
#ifndef HDK
#define HDK 0
#endif
#ifndef RAND_H
#define RAND_H
#include<bits/stdc++.h>
using namespace std;
namespace hdk{namespace Rand{
random_device __rd;
struct __Rand{mt19937_64 _Rand;long long Rand(){return ((_Rand())|(_Rand()<<20))&(_Rand()|_Rand());}int SystemRand(long long a,long long b){return std::rand()%(b-a+1)+a;}int RandSignedInt(){return (int)Rand();}int RandSignedInt(int l,int r){int res=RandSignedInt();while(res<l or res>r) res=RandSignedInt();return res;}int RandInt(){return abs(RandSignedInt());}int RandInt(int a,int b){return abs(RandSignedInt())%(b-a+1)+a;}long long RandSignedLong(){return (long long)Rand();}long long RandSignedLong(long long l,long long r){long long res=RandSignedLong();while(res<l or res>r) res=RandSignedLong();return res;}long long RandLong(){return llabs(RandSignedLong());}long long RandLong(long long a,long long b){return RandLong()%(b-a+1)+a;}unsigned long long device_srand(){unsigned long long seed=__rd();_Rand=mt19937_64(seed);return seed;}unsigned long long time_srand(){unsigned long long seed=time(0);_Rand=mt19937_64(seed);return seed;}void seed_srand(unsigned long long seed=time(0)){_Rand=mt19937_64(seed);}long double RandReal(int fixed){long long res=1;for(int i=1;i<=fixed;++i) res*=10;int rres=RandLong(0,res);cout<<rres<<endl;return rres*1.0/res;}bool access(double access_p){long long res=RandLong();cout<<res<<endl;if(res<=LLONG_MAX*access_p){return true;}return false;}template<typename T>T randfrom(vector<T>A){return A[RandLong(0,(int)A.size()-1)];}template<typename T>T randfrom(T A[],int l,int r){return A[RandLong(l,r)];}
}randt;
struct RandTest{void Balanced_Test(int r,int times,bool display=false){map<int,int>mp;double aver=times*1.0/r,sum=0;while(times--){mp[randt.RandInt(1,r)]++;}for(int i=1;i<=r;++i){if(display) cout<<"["<<i<<","<<mp[i]<<"]"<<endl;sum+=(aver-mp[i])*(aver-mp[i]);}cout<<"[randt Sqrt Dx]: "<<sqrt(sum)<<endl;cout<<endl;}void System_Balanced_Test(int r,int times,bool display=false){map<int,int>mp;srand(__rd());double aver=times*1.0/r,sum=0;while(times--){mp[rand()%r+1]++;}for(int i=1;i<=r;++i){if(display) cout<<"["<<i<<","<<mp[i]<<"]"<<endl;sum+=(aver-mp[i])*(aver-mp[i]);}cout<<"[std::rand Sqrt Dx]: "<<sqrt(sum)<<endl;cout<<endl;}
};
RandTest Test;
}
}
#endif
A.小 Z 的手套
二分答案
考虑如何 check
首先可以想到的是，对数组排序，让大的和大的配是更优的
那么我们可以开一个双指针，每次在不满足当前 check 值的时候移动那个大的数组的指针，直到其中一个指针走到头
此时如果是大的数组的指针走到头则不合法，小的走到头则合法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int l[100001],r[100001];
bool check(int maxn){// cout<<"check "<<maxn<<endl;int j=1;for(int i=1;i<=m;++i){while(llabs(l[j]-r[i])>maxn){// cout<<"out "<<j<<" "<<i<<endl;j++;if(j>n) return false;}// cout<<"pipei "<<j<<" "<<i<<endl;j++;}return true;
}
signed main(){freopen("gloves.in","r",stdin);freopen("gloves.out","w",stdout);// freopen("sample/gloves/ex_gloves4.in","r",stdin);scanf("%lld %lld",&n,&m);for(int i=1;i<=n;++i){scanf("%lld",&l[i]);} for(int i=1;i<=m;++i){scanf("%lld",&r[i]);}sort(l+1,l+n+1);sort(r+1,r+m+1);if(n==m){int ans=0;for(int i=1;i<=n;++i){ans=max(ans,llabs(r[i]-l[i]));}cout<<ans;return 0;}if(n<m){swap(n,m);swap(l,r);}int l=0,r=1e9,ans=-1;while(l<=r){// cout<<l<<" "<<r<<endl;int mid=(l+r)/2;if(check(mid)){r=mid-1;ans=mid;}else{l=mid+1;}}cout<<ans;
}
B.小 Z 的字符串
DP
我们可以考虑直接通过从零开始填，考虑将每个数从当前位置挪到目标位置的花费
有一个性质，就是两个相同的数的相对位置在交换过程中是始终不变的，因此我们直接维护某一个数对应顺序的数字初始位置是多少，直接按照枚举目标顺序转移就行
从头开始填数，设 \(f_{i,j,k,0/1/2}\) 为 \(0/1/2\) 分别有 \(i/j/k\) 个，上一个选择的是 \(0/1/2\) 的最小交换次数
那么现在填到的位置就是 \(p=i+j+k\)，那么需要的交换次数即为 \(|p-p0|\)
显然填数的时候不能与上一位相同，既 \(f_{i,j,k,0}\) 不能从 \(f_{i-1,j,k,0}\) 转移过来，但是可以从 \(f_{i,j,k,1}, f_{i,j,k,2}\) 转移
剩下的同理
#include<bits/stdc++.h>
using namespace std;
class huge{public:auto operator()(char x){return x-'0';}}huge;
string x;
vector<int>pos[3]={{0},{0},{0}};
int f[201][201][201][3];
int cnt[3];
int main(){freopen("string.in","r",stdin);freopen("string.out","w",stdout);cin>>x;for(int i=0;i<=(int)x.length()-1;++i){pos[huge(x[i])].push_back(i+1);lxyt:;}for(int i:{0,1,2}) cnt[i]=(int)pos[i].size()-1;if(max({cnt[0],cnt[1],cnt[2]})>ceil((int)x.length()/2.0)){cout<<-1;return 0;}memset(f,0x3f,sizeof f);memset(f[0][0][0],0,sizeof f[0][0][0]);for(int i=0;i<=cnt[0];++i){for(int j=0;j<=cnt[1];++j){for(int k=0;k<=cnt[2];++k){int p=i+j+k;if(i) f[i][j][k][0]=min(f[i-1][j][k][1],f[i-1][j][k][2])+abs(p-pos[0][i]);if(j) f[i][j][k][1]=min(f[i][j-1][k][0],f[i][j-1][k][2])+abs(p-pos[1][j]);if(k) f[i][j][k][2]=min(f[i][j][k-1][0],f[i][j][k-1][1])+abs(p-pos[2][k]);}}}cout<<min({f[cnt[0]][cnt[1]][cnt[2]][0],f[cnt[0]][cnt[1]][cnt[2]][1],f[cnt[0]][cnt[1]][cnt[2]][2]})/2;
}
C.一个真实的故事
打 abc，Tomorrow update
关注羽田山猫喵
虽然我现在不用
等到差不多 1400 左右就用这个小号打 ABC，感觉现在大号 ABC 收益不大了，按 at 的 rating 机制还是省着点给 ARC
这是什么
小羊可爱捏
