“今天开火车了吗?”——ICPC World Final 队伍的独特训练方法?
发布于 2021-10-10 09:16
总是能听到总决赛的选手们会时常讨论“今天开火车了吗？”，这到底是什么神奇的东西。难道是总决赛队伍所拥有的不为人知的独特训练方法吗？
实际上，“开火车”是我们口中的一个比赛网站。由俄罗斯方面主办的一个网站叫 Opentrain，用很多他们组织的高质量的命题，所以我们一般会直接说成开火车（Train）。
今天，我们来看一套 Opentrain 上相对比较简单的题目。
XIX Russia Team Open, High School Programming Contest
Problem A
温暖的签到题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (LL i=x; i<y; ++i)
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef vector<vi> vvi;
int n;
vvi dat;
vi maxv;
int main() {
scanf("%d", &n);
dat.resize(n);
maxv.resize(n);
int maxs = 0;
FOR (i, 0, n) {
int siz, x;
scanf("%d", &siz);
dat[i].resize(siz);
FOR (j, 0, siz) {
scanf("%d", &dat[i][j]);
maxv[i] = max(maxv[i], dat[i][j]);
}
maxs = max(maxs, maxv[i]);
}
LL ans = 0;
FOR (i, 0, n) {
LL del = 1LL*(maxs-maxv[i])*sz(dat[i]);
ans += del;
}
cout << ans << endl;
return 0;
}
Problem B
字符串签到。
直接拿 map 给每一个字符串编号即可。
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[100010];
map<string,int> M;
struct data
{
string x;
int y;
}a[100010];
bool check(int x,int y)
{
if (x+4>y) return false;
if (s[x]!=92) return false;
if (s[x+1]!='c') return false;
if (s[x+2]!='i') return false;
if (s[x+3]!='t') return false;
if (s[x+4]!='e') return false;
return true;
}
bool cmp(data x,data y)
{
return x.y<y.y;
}
bool check1(char *s)
{
if (s[0]!=92) return false;
if (s[1]!='b') return false;
if (s[2]!='e') return false;
if (s[3]!='g') return false;
if (s[4]!='i') return false;
return true;
}
bool check2(char *s)
{
if (s[0]!=92) return false;
if (s[1]!='e') return false;
if (s[2]!='n') return false;
if (s[3]!='d') return false;
if (s[4]!='{') return false;
return true;
}
int main()
{
gets(s);int S=0;
while(!check1(s))
{
n=strlen(s);
for (int i=0;i<n-4;i++)
if (check(i,n-1))
{
int x=i+6;string y;
while(s[x]!='}') y+=s[x],x++;
M[y]=++S;
}
gets(s);
}
gets(s);int T=0;
while(!check2(s))
{
a[++T].x=s;
n=strlen(s);
if (n>0)
{
for (int i=0;i<n;i++)
if (s[i]=='{')
{
int x=i+1;string y;
while(s[x]!='}') y+=s[x],x++;
a[T].y=M[y];
}
}
gets(s);
}
int flag=0;
for (int i=1;i<=T;i++)
if (a[i].y!=i) {flag=1;break;}
if (!flag) puts("Correct");
else{
puts("Incorrect");
sort(a+1,a+1+T,cmp);
putchar(92);
cout<<"begin{thebibliography}{99}"<<endl;
for (int i=1;i<=T;i++)
cout<<a[i].x<<endl;
putchar(92);
cout<<"end{thebibliography}"<<endl;
}
return 0;
}
Problem C
题意：有一些盒子，每个盒子里有数量，种类不同的物品，每次操作可以把一个物品从一个盒子里移到另一个盒子里，但移动过后每个盒子里的物品种类不能相同，求最少的移动次数，使得物品最多的盒子和最少的盒子的物品数量差最小。
题解：有一个结论，是把东西从物品多的盒子移到物品少的盒子，一定有解。
现在，每次找出物品最多的盒子和物品最少的盒子。如果其物品数相差 ，说明物品数量差已经最小，否则从物品最多的盒子中拿出一个物品放到最少的盒子中，再找最多和最少的盒子，直到满足条件。
问题于是转化为了子问题：维护两个集合，使得每次可以从大集合中快速找出小集合不存在的内容。
可持久化线段树的变种正好能满足这一需求。
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
struct node{
int l,r,siz;
node *ls,*rs;
node(int _l=0,int _r=0,int _s=0){
l=_l; r=_r; siz=_s;
ls=rs=NULL;
}
};
void add(node* nd,int val){
nd->siz++;
if (nd->l==nd->r) return;
int m=(nd->l+nd->r)/2;
if (val<=m){
if (!(nd->ls)) nd->ls=new node(nd->l,m);
add(nd->ls,val);
}
else{
if (!(nd->rs)) nd->rs=new node(m+1,nd->r);
add(nd->rs,val);
}
}
void del(node* nd,int val){
nd->siz--;
if (nd->l==nd->r) return;
int m=(nd->l+nd->r)/2;
if (val<=m) del(nd->ls,val);
else del(nd->rs,val);
}
int sear(node *a,node *b){
if (a->l==a->r){
return a->l;
}
if (!b){
if (a->ls&&a->ls->siz)
return sear(a->ls,NULL);
else return sear(a->rs,NULL);
}
int val=0;
if (a->ls) val+=a->ls->siz;
if (b&&b->ls) val-=b->ls->siz;
if (val>0) return sear(a->ls,b?b->ls:NULL);
else return sear(a->rs,b?b->rs:NULL);
}
struct box{
int id,size;
node *root;
box(int _i=0){
id=_i; size=0; root=new node(1,100000);
}
void insert(int val){
add(root,val);
size++;
}
void erase(int val){
del(root,val);
size--;
}
void clear(){
size=0; root=new node(1,100000);
}
};
int find(box a,box b){
return sear(a.root,b.root);
}
bool operator < (box a,box b){
return a.size<b.size;
}
multiset<box> st;
box bx;
const int maxn=5e5+5;
int ope[maxn][3],siz;
int main(){
int i,j,n,m;
int k,t;
int ans;
multiset<box>::iterator it1,it2;
box u,v;
scanf("%d%d",&n,&m);
for (i=0;i<n;i++){
scanf("%d",&k); bx.clear();
bx.id=i+1;
for(j=0;j<k;j++){
scanf("%d",&t);
bx.insert(t);
}
st.insert(bx);
}
ans=0; siz=0;
while (true){
it1=st.begin(); it2=st.end(); it2--;
if (it2->size-it1->size<=1) break;
u=*it1; v=*it2;
st.erase(it1); st.erase(it2);
t=find(v,u);
v.erase(t); u.insert(t);
ans++; ope[siz][0]=v.id; ope[siz][1]=u.id; ope[siz][2]=t;
siz++;
st.insert(u); st.insert(v);
}
printf("%d\n",ans);
for (i=0;i<siz;i++)
printf("%d %d %d\n",ope[i][0],ope[i][1],ope[i][2]);
return 0;
}
Problem D
题意：给出数对位置，构造两个数列，使得两个数列中一个不含有相同元素，另一个含有两个相同元素，并且这两个数列对于给出的数对位置的比大小的结果都是相同的。
题解：找到一对没有被比较的数对位置，在第一个数列里填上两个相邻的数，在第二个数列里填上相同的数，其他位置随便填就可以了。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=1e5+5;
vector<int> arr[maxn];
int val[maxn];
bool vis[maxn];
int main(){
int i,j,k,n,m;
int u,v,cnt;
scanf("%d%d",&n,&m);
for (i=0;i<m;i++){
scanf("%d%d",&u,&v);
arr[u].push_back(v);
arr[v].push_back(u);
}
for (i=1;i<=n;i++) if (arr[i].size()<n-1){
puts("YES");
for (j=0;j<arr[i].size();j++)
vis[arr[i][j]]=true;
for (j=1;j<=n;j++) if (j!=i&&!vis[j]){
val[i]=1; val[j]=2; cnt=3;
for (k=1;k<=n;k++) if (val[k]==0)
val[k]=cnt++;
for (k=1;k<=n;k++) printf("%d ",val[k]);
puts("");
val[j]=1;
for (k=1;k<=n;k++) printf("%d ",val[k]);
puts("");
return 0;
}
}
puts("NO");
return 0;
}
Problem E
题意：将图上的所有马跳着跳着变成整齐从左下角开始摆放，给出方案。
题解：不要管一个点只能有一个马。冲突了就换一个马走。然后我们可以假定棋盘上只有一个马了，dfs即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
string pos(int x,int y){
string res="";
res+=(char)('a'+x);
res+=(char)('1'+y);
return res;
}
int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={2,1,-1,-2,-2,-1,1,2};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n=8;
vector<vector<int>> board(n,vector<int>(n));
vector<vector<int>> done(n,vector<int>(n));
int k; cin >> k;
for(int i=0;i<k;i++){
string s; cin >> s;
board[s[0]-'a'][s[1]-'1']=1;
}
int X=0,Y=0;
vector<pair<pair<int,int>,pair<int,int>>> v;
vector<pair<int,int>> query(k);
for(int i=0;i<k;i++){
query[i]={X,Y};
if(X+1<n){
X++;
}
else{
Y++;
X=0;
}
}
for(int _=0;_<k;_++){
X=query[_].first,Y=query[_].second;
vector<vector<pair<int,int>>> dp(n,vector<pair<int,int>>(n));
queue<pair<int,int>> q;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dp[i][j]={-1,-1};
if(done[i][j])continue;
if(board[i][j]){
q.push({i,j});
dp[i][j]={i,j};
}
}
}
while(q.size()){
auto p=q.front(); q.pop();
int x=p.first,y=p.second;
for(int i=0;i<8;i++){
int nx=x+dx[i],ny=y+dy[i];
if(0<=nx and nx<n and 0<=ny and ny<n){
if(dp[nx][ny].first!=-1)continue;
dp[nx][ny]={x,y};
q.push({nx,ny});
}
}
}
vector<pair<int,int>> vv;
vv.push_back({X,Y});
int xx=X,yy=Y;
while(1){
pair<int,int> pp={xx,yy};
if(dp[xx][yy]==pp)break;
vv.push_back(dp[xx][yy]);
xx=vv.back().first;
yy=vv.back().second;
}
reverse(vv.begin(), vv.end());
vector<pair<pair<int,int>,pair<int,int>>> skip;
for(int i=0;i+1<vv.size();i++){
if(board[vv[i+1].first][vv[i+1].second]){
skip.push_back({vv[i],vv[i+1]});
// board[vv[i].first][vv[i].second]=0;
// board[vv[i+1].first][vv[i+1].second]=1;
}
else{
v.push_back({vv[i],vv[i+1]});
board[vv[i].first][vv[i].second]=0;
board[vv[i+1].first][vv[i+1].second]=1;
}
}
reverse(skip.begin(), skip.end());
for(auto sk:skip){
v.push_back(sk);
board[sk.second.first][sk.second.second]=1;
board[sk.first.first][sk.first.second]=0;
}
done[X][Y]=1;
}
assert(v.size()<=1500);
cout << v.size() << "\n";
for(auto p:v){
cout << pos(p.first.first,p.first.second) << "-" << pos(p.second.first,p.second.second) << "\n";
}
}
Problem F
题意：每次询问三个下标，给出这三个下标位置的三个数的，求这个数列。
题解：对于四个数，我们不妨假设，那么每次去掉一个数做四次询问，显然这个询问中的最大值+最小值就是这四个数的和，因为在上面的情况中最大+最小。
然后我们对于前五个数，对于每四个数询问出和，就可以得到这五个数的具体情况了，这样一共需要的询问次数是。
然后对于之后的每个数，我们只需要询问他前面三个数和他四个数的和（需要四次询问），即可得到他的准确值。
前五个数的情况，我们用了次，正好，之后的每个数得到都需要次询问，所以总的询问次数正好是，卡着过。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,m;
LL a[1010];
void query(int x,int y,int z,LL &s)
{
//s=Cout(x,y,z);
cout<<"? "<<x<<" "<<y<<" "<<z<<endl;
cin>>s;
}
LL sum4(int a,int b,int c,int d)
{
LL s;
query(a,b,c,s);
LL Max=s,Min=s;
query(a,c,d,s);
Max=max(Max,s),Min=min(Min,s);
query(a,b,d,s);
Max=max(Max,s),Min=min(Min,s);
query(b,c,d,s);
Max=max(Max,s),Min=min(Min,s);
return Min+Max;
}
void init()
{
LL a1234=sum4(1,2,3,4);
LL a1235=sum4(1,2,3,5);
LL a1245=sum4(1,2,4,5);
LL a1345=sum4(1,3,4,5);
LL a2345=sum4(2,3,4,5);
LL sum=(a1234+a1235+a1245+a1345+a2345)/4LL;
a[1]=sum-a2345;a[2]=sum-a1345;
a[3]=sum-a1245;a[4]=sum-a1235;
a[5]=sum-a1234;
}
int main()
{
cin>>n;
init();
for (int i=6;i<=n;i++)
{
LL sum=sum4(i-3,i-2,i-1,i);
a[i]=sum-a[i-3]-a[i-2]-a[i-1];
}
cout<<"! ";
for (int i=1;i<n;i++)
cout<<a[i]<<" ";
cout<<a[n]<<endl;
return 0;
}
Problem I
题意：求一列数中任意一对有序对相乘的最小值。
题解：对于每一个数，找一个他前面比他小的数中最小的，找他后面比他大的数中最大的即可。
显然，这样涵盖了最优解可能产生的位置。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
//#define zerol
//#define terminal
#ifdef zerol
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() {
#ifdef terminal
cout << "\033[39;0m";
#endif
cout << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
int T,n;
LL l,r,a[10000010];
unsigned x,y,z,b[10000010];
int main()
{
cin>>T;
while(T--)
{
cin>>n>>l>>r>>x>>y>>z>>b[1]>>b[2];
for (int i=3;i<=n;i++)
b[i]=b[i-2]*x+b[i-1]*y+z;
for (int i=1;i<=n;i++)
a[i]=((LL)b[i])%(r-l+1LL)+l;
LL Min=a[1],inf=5e18;LL ans=inf;
for (int i=2;i<=n;i++)
{
if (Min<a[i]) ans=min(ans,a[i]*Min);
Min=min(Min,a[i]);
}
LL Max=a[n];
for (int i=n-1;i>=1;i--)
{
if (Max>a[i]) ans=min(ans,a[i]*Max);
Max=max(Max,a[i]);
}
if (ans==inf) puts("IMPOSSIBLE");
else cout<<ans<<endl;
}
return 0;
}
Problem K
题意： 个无限长字符串，由开头和无限次数的循环节构成，求出最少的划分方案，使得划分出的每一个无限字符串集合都互为子序列。
题解：对于循环节，我们只要知道哪些字符在其中出现过就可以了。同样的，对于开头，在末尾的循环节含有的字符都是不需要知道的，可以去掉。而要两个字符串互为子序列，循环节出现过的字符和开头删去末尾循环节包含的字符必须相同。用 map 维护 string 到 vector 上的映射即可（虽然常数可能相当大）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
const int maxn=1e5+5,maxm=1e6+5;
char s1[maxm],s2[maxm];
bool exi[maxn];
string ts;
vector<int> vt;
map<string,vector<int> > mp;
int main(){
int i,j,n;
int len;
map<string,vector<int> >::iterator it;
scanf("%d",&n);
for (i=0;i<n;i++){
scanf("%s%s",&s1,&s2);
memset(exi,false,sizeof(exi));
for (j=0;s2[j]!='\0';j++)
exi[s2[j]-'a']=true;
len=strlen(s1);
while (len>0&&exi[s1[len-1]-'a'])
len--;
s1[len]='\0';
ts=s1;
ts+=' ';
for (j=0;j<26;j++) if (exi[j])
ts+='a'+j;
if (mp.count(ts)) mp[ts].push_back(i+1);
else{
mp[ts]=vt; mp[ts].push_back(i+1);
}
}
printf("%d\n",mp.size());
for (it=mp.begin();it!=mp.end();it++){
printf("%d",it->second.size());
for (i=0;i<it->second.size();i++)
printf(" %d",it->second[i]);
puts("");
}
return 0;
}
Problem L
题意：单周上大小为的教室，双周上大小为的教室，一共周，每个人需要至少上周才能合格，求最大合格人数。
题解：考虑单周、双周、以及所有时间的情况下对人的限制。
设单周有，双周有，显然答案就是。
不过需要注意分母的时候，说明限制没有意义，不需要考虑。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL t,n,a,b,k;
int main()
{
cin>>t>>n>>a>>b>>k;
if (k>n) {puts("0");return 0;}
LL x=(n+1LL)/2LL,y=n/2LL;
LL ans=(a*x+b*y)/k;
if (k-y>0) ans=min(ans,a*x/(k-y));
if (k-x>0) ans=min(ans,b*y/(k-x));
ans=min(ans,t);
cout<<ans<<endl;
return 0;
}
Problem M
题意：对于一个序列，求出其中最长的连续子序列，使得其中任意两个相邻位置的元素都不想等。
题解：在每两个相邻相同元素之间插入隔板，在开头和末尾加上隔板，题目转变为求两个相邻隔板间最大距离，枚举即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn];
int main(){
int i,n,k;
int ans,siz;
scanf("%d%d",&n,&k);
for (i=0;i<n;i++) scanf("%d",&a[i]);
siz=0; b[siz++]=0;
for (i=0;i<n-1;i++) if (a[i]==a[i+1])
b[siz++]=i+1;
b[siz++]=n;
ans=0;
for (i=0;i<siz-1;i++) ans=max(ans,b[i+1]-b[i]);
printf("%d\n",ans);
return 0;
}
ACM算法日常
专注于基础算法的研究工作，5分钟阅读，动画解说每一行源代码。
本文来自网络或网友投稿，如有侵犯您的权益，请发邮件至：aisoutu@outlook.com 我们将第一时间删除。
相关素材