题目地址 https://www.luogu.com.cn/contest/56279#problems
1.符合条件的数
思路:好像没啥坑点,直接暴力枚举,然后把位数计数就行
#include<iostream>
#include<cstdio>
using namespace std;
int n, k;
bool check(int i)
{
int cnt = 0;
while (i)
{
int t = i % 10;
if (t == 3)
cnt++;
i /= 10;
}
if (cnt == k) return true;
return false;
}
int main()
{
scanf("%d %d", &n, &k);
for (int i = n; i <= 2e9; i++)
{
if (check(i))
{
printf("%d", i);
break;
}
}
}
2.选代表
思路:建一个标记数组,边输入边判定看有没有出现过,如果没出现过,输出。
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 110;
bool st[N];//标记数组
int n;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int t;
cin >> t;
if (!st[t])
{
cout << t << " ";
st[t] = 1;
}
}
}
3.成绩统计
思路:用结构体把名字,平时成绩,期末成绩和总成绩存下来,然后stable_sort(根据总成绩排序即可)
坑点:如果两个同学的得分相同,原来输入顺序靠前的,输出时也应当靠前。
sort排序是不稳定的排序,直接sort只能过2/5.使用stable_sort即可
同时注意一下精度转换和输入数据的类型。
补充:稳定排序和不稳定排序
主要是对相同数据排序时出现的问题
比如输入顺序是 a=30 b=30 c=30 (强调一下输入顺序)
sort不稳定排序完是存在 abc acb cab 等等等,这些情况 (虽然都是 30 30 30,但是把输入顺序打乱了)
但是稳定排序的只会根据输入顺序来排序,不会打乱输入顺序,即abc
感觉可能解释的不太明白。。详细解释看百度好了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 110;
int n;
struct SD
{
char s[25];//名字
double a, b, c;
//平时成绩,期末成绩,总成绩
}sd[N];
bool cmp(SD a, SD b)
{
return a.c > b.c;
//把sort排序规则写一下
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> sd[i].s >> sd[i].a >> sd[i].b;
sd[i].b = ceil(sqrt(sd[i].b) * 10);//向上取整
sd[i].c = round(sd[i].b * 0.6 + sd[i].a * 0.4);//四舍五入
}
stable_sort(sd, sd + n,cmp);//注意这里要稳定排序
for (int i = 0; i < n; i++)
{
printf("%s %0.0lf\n", sd[i].s, sd[i].c);//控制输出的格式
}
}
4.背答案
思路:模拟题。好像没啥坑点,用结构体把题库存下来。然后输入一个,遍历一遍题库。
最后那里的i+64是根据acs码把数字转化成大写字母的映射
//4.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 110;
struct KU
{
string pro, ans;
//problem and ans
}k[N];
int n,m;
int main()
{
cin >> n>>m;
for (int i = 0; i < n; i++)
{
cin >> k[i].pro >> k[i].ans;
}
for (int i = 0; i < m; i++)
{
string pb;//输入的问题
cin >> pb;
for (int j = 0; j < n; j++)
{
if (pb == k[j].pro)
{
for (int kk = 1; kk <= 4; kk++)
{
string s;//四个选项
cin >> s;
if (s == k[j].ans)
{
printf("%c\n", kk + 64);//把1 2 3 4 根据asc码转成A B C D
}
}
}
}
}
}
5.击鼓传花
暴力25分,一层优化90,二层优化AC
感觉数据也比较迷,玄学优化就过了
第一次优化的是:用一个bp变量记录一下,上一个位置的值,然后传花之后位置就会改变。
如果大于bp的话就说明还没有转满一轮,就让它继续进行判断
如果小于bp的话就说明转满了一轮,接下来就是在走过的位置一直循环了,这时就可以跳出去了。
第二次优化就是对输入的位置进行判断,如果输入的位置已经拿过花了。
那么接下来的循环就是在走过的位置一直走,可以continue掉
上面就是暴力+优化的写法。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
bool st[N];//拿过花的位置
int n, m, k;
int main()
{
scanf("%d %d %d", &n, &m, &k);
while (m--)
{
int t;
scanf("%d", &t);
if (st[t]) continue;//第二点优化的地方
st[t] = 1;
for (int i = 0; i < n; i++)
{
int bp = t;
t = (t + k) % n;
if (!st[t])
st[t] = 1;
else if (st[t] == 1 && bp > t)//第一点优化的地方
{
break;
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++)
if (!st[i])
cnt++;
printf("%d", cnt);
}
线性筛的思路做
t5可以用线性筛的思维来做,保证 $o(n)$ 就OK了
是直接对判定数组线筛嘛。输入第一个位置后,直接计算它能传到的所有位置,然后打上标记?
我也想到了!不过时间有点紧没写出来 ahhh
对的😂 当时我也犹豫了了一下 猜了下复杂度直接交了结果对了
我感觉比周赛简单多了hh
确实。感觉和div3差不多。都是思维题 ahhh
tql
hh被你逮住了[狗头]