问题 A: 录取分数线
题目描述
新学年,学校将成立信息学兴趣小组提高班。由于指导教师精力有限,只能以选拔考试的成绩为依据,按从高到低的分数,从N个参加选拔的学生中录取不超过M个成员。录取的成员要尽可能地多,但不得超过M个(含M个)。由于可能会有并列分数出现,为了保证公平,有时只得忍痛割爱,可能录取的成员会达不到计划数M。请你编程划定录取分数线。
输入
有N+1行,第一行是报名人数N和录取人数M。以下N行是考试成绩,已按从高到低的顺序排列。N、M和成绩均是1000以内的正整数,N≥M。数据保证不会所有的成绩都相同。
输出
只有1行,为录取分数线。
#include<iostream>
#include<algorithm>
using namespace std;
int a[2000];
int n,m,k;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
if(a[m]!=a[m+1])
cout<<a[m];
else
{
int ok=0;
for(int i=m-1;i>=1;i--)
{
if(a[i]!=a[m])
{
ok=a[i];
break;
}
}
cout<<ok;
}
return 0;
}
问题 B: 电子警察
题目描述
现在很多地方的道路路口都安装了电子警察,即交通违章自动拍照系统。这些系统一般在路口的地下埋设感应线圈,通过传感器判断汽车是否在红灯时通过路面,来控制数码相机自动拍照。在安装这种系统需要挖掘地面,施工麻烦,成本又高。于是有人研究出了同摄像机自动识别车牌并判断违章行为的系统,这样一来,电子警察安装就方便多了,成本也大大降低。请你编程实现其中的一个功能,给出一批某一时间识别后的车牌号码及行进方向,判断该车是否违章,并记录下来。违章的规则设定为:先设置左转、直行、右转依次绿灯通行时间(以秒为单位,只允许一个方向绿灯),先左转绿灯,然后直行绿灯,最后右转绿灯,在其中一个绿灯时,其余两盏灯为红灯状态,假设时间生效在零时整,且给出的数据只限定当天。闯红灯为违章。
输入
第1行有4个整数,以一个空格隔开,依次为左转、直行、右转通行的绿灯持续秒数和识别的车辆数N(1≤N≤10000),后面的N行,表示每辆车的信息,格式为“时间+方向+车牌”,其中时间为6位数字,方向为1个字母(L表示左转,S表示直行,R表示右转),车牌为8个字符,之间没有空格。如081528LZJBB0001,表示车牌号为ZJBB0001的车辆在8时15分28秒左转。
输出
违章车辆的车牌号码,每辆车一行,不含空格,按输进去的先后顺序输出。
把总时间算出来,特判一下t为0的情况,别的没得说
#include<iostream>
#include<cstring>
using namespace std;
int L,S,R,N;
char s[100];
int main()
{
cin>>L>>S>>R>>N;
for(int i=1;i<=N;i++)
{
char k;
scanf("%s",s);
int t=((s[0]-'0')*10+(s[1]-'0'))*3600+((s[2]-'0')*10+(s[3]-'0'))*60+(s[4]-'0')*10+s[5]-'0';
if(t==0)
k='L';
else
{
t%=(L+R+S);
if(t>S+L)
k='R';
else if(t>L)
k='S';
else if(t) k='L';
else k='R'; // t取模之后为0需要特殊判断,这个时候其实是往右转的最后一秒
}
if(s[6]!=k)
{
for(int j=7;j<=14;j++)
printf("%c",s[j]);
printf("\n");
}
}
return 0;
}
问题 C: 查找特定的合数
题目描述
自然数中除了能被1和本身整除外,还能被其他数整除的数叫合数。每个合数都可以写成几个质数相乘的形式,这几个质数都叫做这个合数的质因数。比如8=2×2×2,2就是8的质因数。在1—N(N≤200000)按从小到大顺序排列的自然数序列中,查找第M个有X(2≤X≤6)个不同质因数的合数。例如,第3个有2个不同质因数的合数是12(12只有2、3两个不同的质因数,在12之前有2个不同质因数的合数分别为6和10)。
输入
共1行,分别为M,X。
输出
共1行,为第M个有X个不同质因数的合数。
经过半天的
思考,思路已经有了,首先我们打一个大大的表(我觉得你这个东西在糊弄我,你咋光打表?)wait,wait,打表确实快,打一个素数表,1~1E5+10就可以
- 既然我们要找能分解为x个不同质数的第m个数,那么我们要做的第一步就是分解呗。这就是质数表的左右,本地打好即可(PS:朋哥用欧拉筛法在线筛)我不会欧拉筛,但是我发现打表比欧拉筛快多了(hah...)
- 如果一个数N能被质数Z整除,那么z就是N的一个质因数(这是废话)
- 重点是我们操作N /= Z,然后用新的N继续寻找能整除他的质数,知道质数变小为止,就找完了,而结果就是N能分解为质因数的个数。
- 举个栗子:N=10,tot=0;首先发现N能被质数2整除,ok,tot=1,N/=2 --> N=5;然后我们5不能被质数3整除,继续走,5能被质数5整除,ok,tot=2,N/=5 -->N=1,到此为止,而结果tot=2即是10能分解为的质因数个数;
- 如果有点迷糊的话,我们再举个栗子:N=100,tot=0;首先100能被2整除,tot=1,N/=2 --> N=50;继续:N不能被3整除,继续:N能被5整除:tot=2,N/=5 --> N=10;继续走我们发现10不可能再被大于5的质数整除ok,到此为止,tot=2即是100能分解的质因数个数,即100 = 2^2 + 5^2;
- 明白了以上的道理,问题就基本可以解答了,既然我们能算出所有合数能被分解的质因数的个数,那么,我么就慢慢算,知道算出第M个能分解为X个质因数的合数来就好了啊,珂珂,慢慢来从1枚举到2E5就可以。细节见代码:
感受来自素数表的恐惧吧
素数表的恐惧.jpg
#include<iostream>
#include<cmath>
using namespace std;
int s[18000]={假装打了个素数表};
int isp(int num)
{
if(num < 4)
return 1;
for(int i = 2; i <= sqrt(num) + 1; i++)
if(num % i == 0)
return 0;
return 1;
}
int solve(int num)
{
int tot = 0;
for(int i = 1; s[i] <= num; i++)
if(num % s[i] == 0)
{
num /= s[i];
tot++;
}
return tot;
}
int main()
{
int m,x;
int tot = 0;
cin>>m>>x;
for(int i = 1; i <= 200000; i++)
{
if(isp(i)) //因为我们要算的是合数,那么如果是素数的话直接continue
continue;
if(solve(i) == x) //如果这个合数能分解为,个不同的质因数,那么tot++,这个i也就是第tot个符合的数
tot++;
if(tot == m)
{
cout<<i<<endl; //直到我们找到第m个,输出即可
break;
}
}
return 0;
}
//solve(num),这个函数就是算出num能被分解为几个不同的质因数
//isp(num),这个函数判断num是质数还是合数
黑人问号脸.png
- 这种分解质因数的方法纯属我自己瞎编乱造,不知有没有前辈研究过这样弄,具体思路还可以与我私聊
- 你应该会说:你这个东西又在骗我,素数表呢,咋没有?还假装打了一个,切,我其实想说:
- 所以素数表就交给大家自己打了,不会的话再私聊我。
问题 D: 传话游戏
有向图强连通分量相关问题,正在狂补图论,有兴趣的小伙伴先参照朋哥的题解
- 此题题解终于上线:
- 拆解有向图的强连通分量,然后判断每个点所在的强连通分量里是不是只有自己
- 如果只有自己,那么无环输出 F ,如果不是自己,那么意味着有环,输出 T
- 然后就没有然后了,强连通分量拆解模板题。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 10000;
int n, m;
int scan[1001006];
vector<int> G1[maxn], G2[maxn], S;
int vis[maxn], sccno[maxn], scc_cnt;
void dfs1(int u)
{
if (vis[u])
return;
vis[u] = 1;
for (int i = 0; i < (int)G1[u].size(); i++)
dfs1(G1[u][i]);
S.push_back(u);
}
void dfs2(int u)
{
if (sccno[u])
return;
sccno[u] = scc_cnt;
for (int i = 0; i < G2[u].size(); i++)
dfs2(G2[u][i]);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
if (!scan[a * 1001 + b])
{
scan[a * 1001 + b] = 1;
G1[a].push_back(b);
G2[b].push_back(a); //注意这里不是建立无向图,而是建立另一个反向后的图,跟题目给出的有向图不是一个图。
}
}
scc_cnt = 0;
S.clear();
memset(sccno, 0, sizeof(sccno));
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++)
dfs1(i);
for (int i = n; i > 0; i--)
if (!sccno[S[i]])
{
scc_cnt++;
dfs2(S[i]);
}
memset(scan, 0, sizeof(scan));
for (int i = 1; i <= n; i++)
scan[sccno[i]]++; //把每个强连通分量标号之后,算出每个强连通里面有几个元素
for (int i = 1; i <= n; i++)
{
if (scan[sccno[i]] > 1)
cout << "T" << endl;
else
cout << "F" << endl;
}
return 0;
}
问题 E: 谁是冠军
题目描述
小Q自从参加某小学计算机兴趣小组以来,对编程产生了浓厚的兴趣。他发现用计算机编程不但可以训练思维,还可以解决学习和生活中的一些实际问题。比如,世界杯足球赛时,小Q就经常把其中的一些球队列出来,组成一个小团队,然后根据规则计算积分,并根据积分的高低看看这个团队内谁是冠军。假如某次足球赛的积分规则如下:每胜一局得3分,每平一局得1分,每输一局扣1分,积分最高者为冠军。小Q就想编这样一个程序,输入若干球队的成绩,就能自动求出这个团队中谁是冠军。你也能编一个吗?
输入
输入有两行,第一行是输入的球队数,第二行是每队的比赛成绩,依次为球队编号、胜局数、平局数、负局数(均为小于1000的整数),每个数据间用一空格隔开。输入的数据保证积分各不相同。
输出
只有一个数,就是冠军队的编号。
结构体成员排序,没得说
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct man
{
int a;
int b;
int c;
int d;
}s[2000];
int n;
bool cmp(man x,man y)
{
return (3*x.b+x.c-x.d)>(3*y.b+y.c-y.d);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d%d%d%d",&s[i].a,&s[i].b,&s[i].c,&s[i].d);
}
sort(s,s+n,cmp);
cout<<s[0].a;
return 0;
}
问题 F: 搭积木的诀窍
题目略,先发现每层数字递推规律,然后就没有然后了...强制推送一波“打表”操作,虽然可以更简便的直接算...
#include<iostream>
using namespace std;
int b[105]={1,4,10,20,35,56,84,120,165,220,286,364,455,560,680,816,969,1140,1330,1540,1771,2024,2300,2600,2925,3276,3654,4060,4495,4960,5456,5984,6545,7140,7770,8436,9139,9880,10660,11480,12341,13244,14190,15180,16215,17296,18424,19600,20825,22100,23426,24804,26235,27720,29260,30856,32509,34220,35990,37820,39711,41664,43680,45760,47905,50116,52394,54740,57155,59640,62196,64824,67525,70300,73150,76076,79079,82160,85320,88560,91881,95284,98770,102340,105995,109736,113564,117480,121485,125580,129766,134044,138415,142880,147440,152096,156849,161700,166650,171700};
int main()
{
int k,n;
cin>>n;
for(int i=0;i<=100;i++)
if(b[i]>n)
{
k=i;
break;
}
cout<<k<<endl<<n-b[k-1];
return 0;
}
问题 G: 卡布列克常数
题目描述
最近,小Q在数学兴趣课中了解了“卡布列克常数”。卡布列克是一位数学家,他在研究数字时发现:任意一个不是用完全相同数字组成的四位数,如果对它们的每位数字重新排序,组成一个最大的数和一个最小的数,然后用最大数减去最小数,差不够四位数时补零,类推下去,最后将变成一个固定的数:6174,这就是卡布列克常数。
例如:4321-1234=3087
8730-378=8352
8532-2358=6174
7641-1467=6174
……
小Q想,我能不能编程来验证呢?输入一个符合条件的四位数,然后验证运算过程。
输入
共1行,为任意一个不是用完全相同数字组成的四位数。
输出
变为卡布列克常数的运算过程,由若干行组成,每行是一个算式,不含空格。
传说中的“数字黑洞”,真的很神奇...直接把数字每一位分离排序即可,这里用字符数组操作,显得更直观,但有伤简洁之道...
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char s[10];
int ans;
int now=-1;
int ok[10000];
int main()
{
cin>>s[0]>>s[1]>>s[2]>>s[3];
sort(s,s+4);
while(1)
{
sort(s,s+4);
int mx=(s[3]-'0')*1000+(s[2]-'0')*100+(s[1]-'0')*10+(s[0]-'0');
int mn=(s[3]-'0')+(s[2]-'0')*10+(s[1]-'0')*100+(s[0]-'0')*1000;
now=mx-mn;
if(ok[now])
break;
else
{
cout<<mx<<"-"<<mn<<"="<<mx-mn<<endl;
ok[now]=1;
}
s[0]=now%10+'0';
s[1]=now/1000+'0';
s[2]=now%1000/100+'0';
s[3]=(now%1000/10%10)+'0';
}
return 0;
}
问题 H: 扫雷游戏
- 首先明确一点:如果一个点以及他的前一个点已经确定有无地雷,那么这个点之后的一个点一定可以确定有无地雷。想一想为什么?
- 如果发现这个规律,我么可以凭借这个递推关系把所有的点都推出,而问题在于第一个点怎么办?假设!
- 我们假设第一个点有地雷,那么依照递推关系所有的点都能够推出答案,如果发现某个点有矛盾,那么就是我们假设错误,我们回到起点假设第一个点没地雷,那么我们一定可以得出正确答案。
- 而递推的的判断矛盾的条件很简单,因为第 i 点和第 i - 1 点,都是locked状态,明白了吧?
- 细节见代码
#include<iostream>
#include<cstring>
using namespace std;
int n,sum;
int a[1000]; //a[i]表示题目给的i位置的数据
int b[1000]; //b[i]表示i位置是否有雷
void input()
{
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i];
}
int run1() //尝试第一种方案,在第一个位置放雷
{
b[1] = 0;
for(int i = 1; i <= n; i++)
{
//判断是否矛盾,如果矛盾直接返回false就可以
if((b[i] + b[i-1] > a[i]) || (b[i] + b[i-1] == a[i]-2) || ((b[i]+b[i-1] == a[i]-1) && i==n))
return 0;
else if(b[i] + b[i-1] == a[i]-1)
b[i+1] = 1;
}
return 1;
}
void run2() //尝试第二种方案,第一个位置不放雷
{
memset(b,0,sizeof(b));
for(int i = 1; i <= n; i++)
if(b[i] + b[i-1] == a[i] - 1)
b[i+1] = 1;
}
int main()
{
input(); //输入数据
if(!run1()) //如果第一种方案矛盾,那么不用考虑,答案一定能通过第二种方案推出
run2();
for(int i = 1; i <= n; i++)
{
cout<<b[i];
if(b[i])
sum++;
}
cout<<endl<<sum;
return 0;
}
本次参训感想
- me:终于又到了发表参训感想的时候了。咳咳,来,让我说几句:
- me: I just want to say something for the test...
image.png
- teacher: Wait, wait ,I just want to show you a picture:
- me:emm.....
- teacher:emm.....
- 沉默良久后,来自我肺腑深处的良知终于迸发出来:woc!
网友评论