[codeforces] 暑期训练之打卡题（一）
2024-09-18 02:22:03
每个标题都做了题目原网址的超链接
Day1《Vanya and Lanterns》
题意：
一条长度为 l 的街道，在这条街道上放置了n个相同的灯，街道一端位置记为0，每个灯的位置在ai处，问灯的最小照射半径为多少时，才能满足整条街道都能被灯光照到 。
题解：
- 输入所有的灯的位置，然后进行排序。
- 比较每两个相邻的灯的距离，取最大值的 1/2。
- 比较两端的值：第一个灯需要照到 0 位置，最后一个灯需要照到 l 位置。
- 三个值中取最大值。
上板子：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[1005];
int i, n, l;
double ant;
cin >> n >> l;
for (int i = 0;i < n;i++)
{
cin >> a[i];
}
sort(a, a + n);//这里我为了偷懒用了sort，根据题意考察的是二分法
ant = a[0] > (l - a[n - 1]) ? a[0] : (l-a[n - 1]);//使用条件运算符取较大值
for (int i = 1;i < n;i++)
{
ant = (a[i] - a[i - 1])/2.0 > ant ? (a[i] - a[i - 1])/2.0 : ant;
}
printf("%.10f\n", ant);//保留10位小数输出
return 0;
}
Day2《K-th Not Divisible by n》
题意：
对于n这个数字，求第k个不能整除n的数字。
题解：
- 当 k < n 时，ans = k
- 当 k = n 时，ans = n + 1 = k + 1
- 当 k > n 时，if (k % (n - 1) == 0) ans = k / (n - 1) * n - 1; else ans = k / (n - 1) * n + (k % (n - 1));
- 总结：ans = k + (k-1) / (n-1)
上板子：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
long long n, k,ans;
cin >> n >> k;
ans = k+((k-1)/(n-1));
cout << ans<<endl;
}
return 0;
}
Day3.1《Worms》
题意：
给出n个区间长度，如 2,3,4 则表示区间 [1,2]、[3,5]、[6,9]。再给出m个数字，问这些数分别在哪个区间。
题解：
- 建立一个初始值为0的数组b，表示每个数字位于哪个区间
- 每次加大区间长度时，给b赋值标记位于某个区间
- 详见代码注释
上板子：
#include<bits/stdc++.h>
using namespace std;
int b[1000000] = { 0 };//依照题意，区间不大于e6
int main()
{
int n, a = 1, cnt = 1;//cnt表示第几个区间
cin >> n;
int c;
cin >> c;
for (int j = 1;j <= c;j++)
b[j] = cnt;
cnt++;
a = c;//由于第一个数据较为特殊，不符合下述循环中的普遍规律，故单独处理
for (int i = 1;i < n;i++)
{
cin >> c;
int d = a + c;//输入新的区间大小后，新的区间的最大值
for (int j = a + 1;j <= d;j++)//新的区间最小值应由上个区间的最大值+1组成
b[j] = cnt;//将位于该区间的所有数字赋权为cnt
cnt++;
a = d;//a改为该区间的最大值，进入下次循环
}
int t;
cin >> t;
while (t--)
{
int value;
cin >> value;
cout << b[value] << endl;
}
return 0;
}
Day3.2《IQ test》
题意：
找到n个数中奇偶性不同的一个数并输出该数的输入时的顺序位次。
题解：
- 如果是奇数，如果q=0，令q=1，记录该数字
- 偶数同理
- 最后判一下奇偶哪个只出现了一次输出就行
上板子：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int p = 0, q = 0, ans1=0, ans2=0;
for (int i = 1;i <= n;i++)
{
int a;
cin >> a;
if (a % 2 == 0)
{
if (p > 0)ans1 = 0;//该串数中偶数，不止一个，则令ans1=0
else//如果该数是第一个偶数，则需记录该数顺序位次（ans1=i）
{
ans1 = i;
p = 1;
}
}
else//奇数同理
{
if (q > 0)ans2 = 0;
else
{
ans2 = i;
q = 1;
}
}
}
if (ans1)cout << ans1;//输出非零数
else cout << ans2;
return 0;
}
Day4《Registration System》
题意：
输入n个字符串s，若s第一次出现，则输出OK，不是则输出si（i=1,2,3...）
题解：
- 本题用了STL中的map知识，本来以为我写了博客的后来发现没写，所以这里就不贴地址了，可以自己去搜一下 map 的知识哈（这两天有兴趣的话可能会写吧）
- 将 si 视为字符串 s 和整数型 i，那么 i 为 该字符串 s 出现的次数 - 1
上板子：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
map<string, int> p;//建立一个 map，存储 字符串string 及 出现次数int
while (n--)
{ cin >> s;
if (p[s] != 0)
{
cout << s << p[s] << endl;//如果不是第一次出现，先输出s再输出次数
p[s]++;
}
else
{
cout << "OK" << endl;
p[s] = 1;
}
}
return 0;
}
Day5《Same Differences》
题意：
给你 t 个由 n 个整数组成的数组，计算索引对（i，j）使得 i < j 并且 aj − ai = j − i，输出每个数组符合要求的索引对的个数
题解：
- 将条件 aj − ai = j − i 转化为 ai - i = aj - j，那么题目中的要求就变成了 i < j 和 ai - i = aj - j
- 本题代码使用C++STL中的map知识，没学过的可以去网络搜一下
- 利用 map<int,int> 存储 ai - i 的值的个数
- 假设 ai - i = k，k对应的个数有n个，那么对于该n个数，一共能组成 n*(n-1)/2 个索引对（需要满足 i < j）
- 累加所有情况
代码中对于上述步骤4、5略有改变，实现了通过一次循环而非多次循环解决问题，详见代码
上板子：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
int n, k;
int t;
cin >> t;
while (t--)
{
ll ans = 0;
map < int, int > a;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> k;
k -= i;//值-下标，即题目中的ai-i
ans += a[k];//该数能与之前录入的每个满足ai-i数据组成索引对
a[k]++;//利用map，记录ai-i相等的值的个数
}
cout << ans << endl;
}
return 0;
}
Day6《Odd Selection》
题意：
从长度为n的给定数组中挑出x个数使总和为奇数，输出能（YES）或不能（NO）
题解：
- 分别记录数组中奇数与偶数的个数
- 要使得总和为奇数，那么要满足三个条件：
- 需要有 i 个偶数，且 i 小于偶数个数
- 需要有 x - i个奇数，且x-i 小于奇数个数
- x-i 必须也是奇数
上板子：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, x, a;
cin >> n >> x;
string ans = "NO";
int num1 = 0, num2 = 0;
for (int i = 0;i < n;i++)
{
cin >> a;
if (a % 2 == 0)num1++;//偶数个数
else num2++;//奇数个数
}
for (int i = 0;i < x;i++)
if (i <= num1 && x - i <= num2 && (x - i) % 2 == 1)
{
ans = "YES";
break;//若有一组满足条件则结束循环
}
cout << ans << endl;
}
return 0;
}
Day7《AquaMoon and Stolen String》
题意：
给你n个字符串，每个字符串的长度均为m，再给你n-1个字符串，通过多次执行交换两个字符串对应的位置的字符操作，一定会有n-1对字符串相等，求最后剩下不能配对的字符串。
题解：
两组字符串总的字母数的差值就是少的字符串
先把第一组的所有字母存起来
然后减去第二组的字母
剩下的就是答案
上板子：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int cnt[100003][26];
int main() {
int T;
cin >> T;
while (T--)
{
memset(cnt, 0, sizeof(cnt));
int n, m;
cin >> n >> m;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0; j < m; j++)
cnt[j][s[j] - 'a']++;
}
for (int i = 0; i < n - 1; i++) {
cin >> s;
for (int j = 0; j < m; j++)
cnt[j][s[j] - 'a']--;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 26; j++) {
if (cnt[i][j]) {
cout << char(j + 'a');
break;
}
}
}
cout << endl;
}
return 0;
}
Day8《AquaMoon and Strange Sort》
题意：
题意大概是，首先给出n个数字，每个数字最初对应的方向都是向右，然后我们要把他们排成一个非递减数列，每次只能交换相邻的两个数字，并且交换后，他们的方向都会变（向右变成向左，向左变成向右），如果有一种可能，变化到非递减数列后，每一个数字对应的方向仍然都是向右，那么输出yes，否则输出no。
题解：
本题每一个数字变化时，方向都会反过来
所以如果想要方向都向右的话，每一个数字变化完，他们交换的次数一定是偶数次
如果它一开始在奇数位置上，那么最终如果合法，它的位置仍然会是奇数位置
上板子：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
int a[maxn];
int cnt[maxn][2];
int main()
{
int t;
cin >> t;
while (t--)
{
memset(cnt, 0, sizeof cnt);
int n;
cin >> n;
for (int i = 1; i <= n;i++)
{
cin >> a[i];
cnt[a[i]][i % 2]++;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n;i++)
{
cnt[a[i]][i % 2]--;
}
bool flag = 1;
for (int i = 1; i <= n;i++)
{
if (cnt[a[i]][0] || cnt[a[i]][1])
{
flag = 0;
break;
}
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
Day9《T-primes》
题意：
T-素数：一个数 t 的因数只有1、t1/2、t，则称这个数为T-素数。
题解：
思路一：
由于题目中给定的数为1~e12，故可先用埃氏筛，筛选所有1-e6的素数并存储
然后每输入一个数，判断 sqrt(t) 是否为素数即可
思路二：
- 同样使用埃氏筛对1~e6进行素数筛选
- 建立一个 set 容器，把所有素数的平方存储
- 使用 set 容器中的 count 判断否为T-素数即可
上板子（思路一）：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1000005;
bool b[M];//都定义为全局变量，可以在主函数里调用
int p[M], cnt = 0;//p用于存储m以内的全部素数，cnt为个数
void k()
{
memset(b, 1, sizeof(b));
b[1] = 0;
for (int i = 2; i < sqrt(M); i++)//判断M以内的各个数字是否为素数
{
if (b[i])
{
cnt++;//用于记录p中有几个数据
p[cnt] = i;//p[ ]用于存储各个<=M的素数
for (int j = i * i; j < M; j += i)//一定要判断j<=m，保证数组不会爆
{
b[j] = 0;//i 存储的是素数，j 为某素数的倍数，这个数一定不是素数
}
}
}
}
int main()
{
k();//因为前面是全局变量所以使用函数后面能够调用
int n;
cin >> n;
for (int i = 1;i <= n;i++)
{
ll m;
cin >> m;
double k = sqrt(m);
if (k == int(k) && b[int(k)])cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
Day10《Two Buttons》
题意：
求 n 转换到 m 的步骤数，n只能 *2 或者 -1
题解：
- 当 n > m 时，ans = n - m
- 当 n < m 时，我选择的是让 m 通过 /2 或者 +1 来变成 n
- 规律：
如果 m 是奇数，那么必然最后一步是 -1，因此可以先加回去，把 m 变成 m+1
如果 m 是偶数，那么必然最后一步是 *2，也可以还原，把 m 变成 m/2
上板子：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int ans = 0, n, m;
while (cin >> n >> m) {
ans = 0;
if (n > m) cout << n - m << endl;
else
{
while (n < m)
{
if (m % 2 == 1)
{
m++;
ans++;
}
m /= 2;
ans++;
}
ans += n - m;
cout << ans << endl;
}
}
return 0;
}
暑假codeforces打卡系列（一）完
最新文章
- 【代码笔记】iOS-页面调的时候隐藏工具条
- ffmpeg centos6.5上安装(测试 amr 转换为 mp3)
- 44、NLP的其他分词功能测试
- C#中SQL Server数据库连接池使用及连接字符串部分关键字使用说明
- .net破解二(修改dll)
- Tutorial: Analyzing sales data from Excel and an OData feed
- HTML5 Canvas画数字时钟
- 查看sql server数据库各表占用空间大小
- JQuery EasyUI 对话框的使用方法
- VS2010安装与测试编译问题（fatal error LNK1123: failure during conversion to COFF: file invalid or corrupt）
- 使用NPOI导出图片到EXCEL
- js定时刷新页面.
- 关于下拉列表HtmlDownlistFor的使用
- floyd求最小环
- Java 的 Api 文档生成工具 JApiDocs 程序文档工具
- javascript 值类型和引用类型
- java基础篇之理解synchronized的用法
- Elasticsearch学习之快速入门案例
- Python学习过程笔记整理（四）
- [转载]LeetCode: Gray Code