题目列表
智商测试
题目数据有点小问题，$t\leq6000$。
但问题不大。
首先最暴力的办法是枚举每个时间点，模拟题意。
我就这么做的。
复杂度 $\mathcal O(t)$ 可以接受。
其次，如果有吊打我的实力能写数学办法，那就是确定行确定列，随便写写。
printf("%d %d\n",t/n%n+1,t%n+1); 即可，复杂度 $\mathcal O(1)$。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n,t,x=1,y=1;
scanf("%d%d",&n,&t);
while(t)
{
if(x==n&&y==n)x=y=1;
else if(y!=n)y++;
else x++,y=1;
t--;
}
printf("%d %d\n",x,y);
return 0;
}灵石采集
一个简单贪心。
首先，如果费用大于等于价值，我们不走，走了也不挣钱。
其次我们对于费用小至大排序，每次能花费就花费并且拿这个点的价值。
复杂度只有排序的 $\mathcal O(n \log n)$。
代码
#include<bits/stdc++.h>
using namespace std;
int N,k,n;
struct node
{
int v,w;
}a[114514];
bool cmp(node a,node b)
{
if(a.w!=b.w)return a.w<b.w;
return a.v>b.v;
}
int main()
{
freopen("collect.in","r",stdin);
freopen("collect.out","w",stdout);
scanf("%d%d",&N,&k);
for(int i=1;i<=N;i++)
{
int v,w;
cin>>v>>w;
if(v>w)a[++n]=(node){v,w};
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(k>a[i].w)k+=(a[i].v-a[i].w);
}
cout<<k<<endl;
return 0;
}足球队
一道中等模拟，难点在字符串处理。
有个坑点，是需要选出选手之后再选队长，不是先安排队长。
代码主函数很清楚，函数压了一下行，完整函数可以在
这里
void read()
{
for(int i=1;i<=22;i++)
{
getline(cin,player[i].infor);
player[i].infor+=' ';
player[i].year=0;
/*cout<<player[i].infor<<endl;*/
int j=0;
int id=0;
for(;player[i].infor[j]!=' ';j++)
{
id=id*10+(player[i].infor[j]-'0');
}
player[i].id=id;
j++;
string name;
for(;player[i].infor[j]!=' ';j++)
{
name+=player[i].infor[j];
}
player[i].name=name;
j++;
player[i].role=player[i].infor[j];
j+=2;
// for(;player[i].infor[j]==' ';j++)
while(j<player[i].infor.size())
{
int StartYear=0,EndYear=0;
for(;player[i].infor[j]!='-';j++)
{
StartYear=StartYear*10+(player[i].infor[j]-'0');
// cout<<player[i].infor[j]<<"Year:"<<StartYear<<'\n';
//
}
j++;
for(;player[i].infor[j]!=' ';j++)
{
EndYear=EndYear*10+(player[i].infor[j]-'0');
}
j++;
player[i].year+=EndYear-StartYear+1;
// cout<<player[i].year<<endl;
}
}
cin>>plan;
plan+='-';
int j=0;
/*
D后卫
*/
for(;plan[j]!='-';j++)
{
D=D*10+(plan[j]-'0');
}
j++;
/*
M中场
*/
for(;plan[j]!='-';j++)
{
M=M*10+(plan[j]-'0');
}
j++;
/*
S前锋
*/
for(;plan[j]!='-';j++)
{
S=S*10+(plan[j]-'0');
}
j++;
/*cout<<D<<" "<<M<<" "<<S<<endl;*/
}
bool cmp_of_role(node a,node b)
{
if(a.role!=b.role)return a.role<b.role;
return a.id<b.id;
}
string to_str(int x)
{
string ret="";
while(x)
{
ret+=char(x%10+'0');
x/=10;
}
reverse(ret.begin(),ret.end());
return ret;
}
void sort_them()
{
sort(player+1,player+22+1,cmp_of_role);
for(int i=1;i<=22;i++)
{
switch(player[i].role)
{
case 'S':
{
a[0].push_back(player[i]);
break;
}
case 'M':
{
a[1].push_back(player[i]);
break;
}
case 'D':
{
a[2].push_back(player[i]);
break;
}
case 'G':
{
a[3].push_back(player[i]);break;
}
}
}
}
void choose()
{
ans[1]=NoNo;
if(a[3].size()<G){ok_plan=0;return;}
if(a[2].size()<D){ok_plan=0;return;}
if(a[1].size()<M){ok_plan=0;return;}
if(a[0].size()<S){ok_plan=0;return;}
cnt=1;
for(auto i:a[3])
{
cnt++;
ans[cnt]=i;
if(cnt==G+1)break;
}
for(auto i:a[2])
{
cnt++;
ans[cnt]=i;
if(cnt==G+D+1)break;
}
for(auto i:a[1])
{
cnt++;
ans[cnt]=i;
if(cnt==G+D+M+1)break;
}
for(auto i:a[0])
{
cnt++;
ans[cnt]=i;
if(cnt==G+D+M+S+1)break;
}
int z=0,Y=-1,id=-1;
for(int i=2;i<=12;i++)
{
if(ans[i].year>=Y)
{
if(ans[i].year==Y)
{
if(ans[i].id>id)z=i,Y=ans[i].year,id=ans[i].id;
}
else
{
z=i,Y=ans[i].year,id=ans[i].id;
}
}
}
swap(ans[z],ans[1]);
}
void print()
{
if(!ok_plan)
{
puts("IMPOSSIBLE TO ARRANGE");
return;
}
for(int i=1;i<=12;i++)
{
if(ans[i].id!=-1)cout<<to_str(ans[i].id)<<' '<<ans[i].name<<' '<<ans[i].role<<'\n';
}
}代码
#include<bits/stdc++.h>
#define NoNo (node){"-1",-1,"-1",'!',-1}
using namespace std;
struct node
{
string infor;
int id;
string name;
char role;
int year;
}player[50];
node ans[20];
vector<node>a[4];
int S,M,D,G=1,cnt=0;
/*
S前锋 0
M中场 1
D后卫 2
G守门员 3
*/
bool ok_plan=1;
string plan;
string to_str(int x){string ret="";while(x){ret+=char(x%10+'0');x/=10;}reverse(ret.begin(),ret.end());return ret;}
bool cmp_of_role(node a,node b){if(a.role!=b.role)return a.role<b.role;return a.id<b.id;}
void read(){for(int i=1;i<=22;i++){getline(cin,player[i].infor);player[i].infor+=' ';player[i].year=0;/*cout<<player[i].infor<<endl;*/int j=0;int id=0;for(;player[i].infor[j]!=' ';j++){id=id*10+(player[i].infor[j]-'0');}player[i].id=id;j++;string name;for(;player[i].infor[j]!=' ';j++){name+=player[i].infor[j];}player[i].name=name;j++;player[i].role=player[i].infor[j];j+=2;while(j<player[i].infor.size()){int StartYear=0,EndYear=0;for(;player[i].infor[j]!='-';j++){StartYear=StartYear*10+(player[i].infor[j]-'0');}j++;for(;player[i].infor[j]!=' ';j++){EndYear=EndYear*10+(player[i].infor[j]-'0');}j++;player[i].year+=EndYear-StartYear+1;}}cin>>plan;plan+='-';int j=0;/*D后卫*/for(;plan[j]!='-';j++){D=D*10+(plan[j]-'0');}j++;/*M中场*/for(;plan[j]!='-';j++){M=M*10+(plan[j]-'0');}j++;/*S前锋*/for(;plan[j]!='-';j++){S=S*10+(plan[j]-'0');}j++;/*cout<<D<<" "<<M<<" "<<S<<endl;*/}
void sort_them(){sort(player+1,player+22+1,cmp_of_role);for(int i=1;i<=22;i++){switch(player[i].role){case 'S':{a[0].push_back(player[i]);break;}case 'M':{a[1].push_back(player[i]);break;}case 'D':{a[2].push_back(player[i]);break;}case 'G':{a[3].push_back(player[i]);break;}}}}
void choose(){ans[1]=NoNo;if(a[3].size()<G){ok_plan=0;return;}if(a[2].size()<D){ok_plan=0;return;}if(a[1].size()<M){ok_plan=0;return;}if(a[0].size()<S){ok_plan=0;return;}cnt=1;for(auto i:a[3]){cnt++;ans[cnt]=i;if(cnt==G+1)break;}for(auto i:a[2]){cnt++;ans[cnt]=i;if(cnt==G+D+1)break;}for(auto i:a[1]){cnt++;ans[cnt]=i;if(cnt==G+D+M+1)break;}for(auto i:a[0]){cnt++;ans[cnt]=i;if(cnt==G+D+M+S+1)break;}int z=0,Y=-1,id=-1;for(int i=2;i<=12;i++){if(ans[i].year>=Y){if(ans[i].year==Y){if(ans[i].id>id)z=i,Y=ans[i].year,id=ans[i].id;}else{z=i,Y=ans[i].year,id=ans[i].id;}}}swap(ans[z],ans[1]);}
void print(){if(!ok_plan){puts("IMPOSSIBLE TO ARRANGE");return;}for(int i=1;i<=12;i++){if(ans[i].id!=-1)cout<<to_str(ans[i].id)<<' '<<ans[i].name<<' '<<ans[i].role<<'\n';}}
int main()
{
freopen("footballteam.in","r",stdin);
freopen("footballteam.out","w",stdout);
read();
// cout<<player[6].year<<" "<<player[10].year<<endl;
// for(int i=1;i<=22;i++)cout<<player[i].year<<endl;
sort_them();
choose();
print();
return 0;
}
/*
9 PlayerA M 2000-2001 2003-2006
2 PlayerB M 2004-2006
10 PlayerC D 2001-2005
1 PlayerD D 2000-2001 2002-2004
11 PlayerE S 2003-2006
8 PlayerF M 2005-2006
22 PlayerG S 2005-2006
25 PlayerH G 2000-2001 2002-2003 2005-2006
6 PlayerI D 2003-2006
26 PlayerJ D 2003-2004 2000-2001
18 PlayerK M 2003-2004
19 PlayerL M 2000-2001 2003-2006
7 PlayerM S 2003-2006 1999-2001
21 PlayerN S 2003-2006
13 PlayerO S 2005-2006
15 PlayerP G 2001-2006
14 PlayerQ D 2003-2004
5 PlayerR S 2000-2005
20 PlayerS G 2000-2002 2003-2003
12 PlayerT M 2004-2005
3 PlayerU D 2000-2005
4 PlayerZ M 2001-2004
4-4-2
*/波浪数
一眼丁真，鉴定为我不会的 dp。
但我写了个大概率错的贪心过了……？
首先观察到这一定是按 大小大小大小大... 或 小大小大小大小 排列的。
我们讨论是大开头还是小开头，不符合规律就干掉它修改并且算一次次数。
输出时取个最小值即可。
PS：欢迎巨佬们出反例 hack 我这个贪心。
代码
#include<bits/stdc++.h>
using namespace std;
const int Maxx=1e9+1;
const int Minn=-1;
int Max,Min;
int n;
int a[114514];
int f[114514];
int b[114514];
int main()
{
freopen("wave.in","r",stdin);
freopen("wave.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
int cur,ans;
/*plan A*/
cur=0;
memset(f,0,sizeof(f));
f[1]=-1;
for(int i=2;i<=n;i++)
{
f[i]=(i&1?-1:1);
if(f[i-1]==-1)
{
if(a[i]>=a[i-1])
{
cur++;
a[i]=Minn;
}
}
if(f[i-1]==1)
{
if(a[i]<=a[i-1])
{
cur++;
a[i]=Maxx;
}
}
}
ans=cur;
// for(int i=1;i<=n;i++)cout<<a[i]<<" ";
// cout<<endl;
/*plan B*/
cur=0;
memset(f,0,sizeof(f));
f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=(i&1?1:-1);
if(f[i-1]==-1)
{
if(b[i]>=b[i-1])
{
cur++;
b[i]=Minn;
}
}
if(f[i-1]==1)
{
if(b[i]<=b[i-1])
{
cur++;
b[i]=Maxx;
}
}
}
// for(int i=1;i<=n;i++)cout<<b[i]<<" ";
// cout<<endl;
cout<<min(ans,cur)<<endl;
return 0;
}
/*
6
1 1 2 2 3 3
11
703 702 703 703 702 703 702 702 702
700 702
*/