有 个人编号为 ,在圆桌前为围成了一个圈。 号的下一个人就是 号。
每个人都有一个名字 和年龄 。没有相同的名字或者相同的年龄。
请找到年纪最小的人,并由他开始按顺序输出每个人的名字。
#include <bits/stdc++.h>
using namespace std;
int n;
string nam[105];
int age[105];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int pos = 1;
for (int i = 1; i <= n; i++)
{
cin >> nam[i] >> age[i];
if (age[i] < age[pos])
pos = i;
}
for (int i = pos; i <= n; i++)
cout << nam[i] << "\n";
for (int i = 1; i < pos; i++)
cout << nam[i] << "\n";
return 0;
}
给定一个正整数 ,如果 ,就输出 ,否则把除最高的三位的数位变为 后输出。
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int now = 1;
for (int i = 1000; i <= 100000000; i *= 10)
{
if (n >= i)
n = n - (n / now % 10) * now;
now *= 10;
}
cout << n << "\n";
return 0;
}
有 个人在平面直角坐标系上,第 个人所处的位置是 。
如果两个人的距离小于等于 就会发生病毒传染。
第一个人感染了病毒,问足够长的时间后,每个人是否会感染上病毒。
数据范围小,并查集或者直接爆搜都可以。
#include <bits/stdc++.h>
using namespace std;
int n, d;
int x[2005], y[2005];
int fa[2005];
int findFa(int x)
{
if (x == fa[x])
return x;
return fa[x] = findFa(fa[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> d;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i];
fa[i] = i;
}
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= d * d)
{
int faI = findFa(i);
int faJ = findFa(j);
if (faI != faJ)
{
fa[faI] = faJ;
}
}
}
}
int bad = findFa(1);
for (int i = 1; i <= n; i++)
{
if (findFa(i) == bad)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
平面直角坐标系上有一个矩形的大蛋糕,蛋糕左下角坐标为
,右上角坐标为 。
有 个草莓,第 个草莓位于 ,保证任何两个草莓都在不同的位置,且 、.
现在 Taka 会把蛋糕进行分切。
首先会竖直切 刀,第 刀且在 这条线上。保证 .
然后会水平切 刀,第 刀且在 这条线上。保证 .
这样草莓就被分为了 块。问草莓最多的蛋糕有几颗草莓,草莓最少的蛋糕又有几颗草莓。
肯定不可能看每块蛋糕,切入点为考虑每颗草莓在哪块蛋糕上。
离散化或者二分(我是二分做的)都能得到第 颗草莓所在的蛋糕编号 。
现在问题就是 中最多/最少有几个相同的。
排序后简单 扫一遍就可以完成统计了。当然也可以离散化后统计,或者 map
来统计,或者排序后二分统计都可以。
需要注意特判一下会不会有蛋糕上没有草莓。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int w, h;
int n;
int p[212345], q[212345];
int A;
int a[212345];
int B;
int b[212345];
int id[212345];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> w >> h;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i] >> q[i];
cin >> A;
for (int i = 1; i <= A; i++)
cin >> a[i];
A++;
a[A] = w;
cin >> B;
for (int i = 1; i <= B; i++)
cin >> b[i];
B++;
b[B] = h;
for (int i = 1; i <= n; i++)
{
int nowX = upper_bound(a + 1, a + A + 1, p[i]) - a;
int nowY = upper_bound(b + 1, b + B + 1, q[i]) - b;
id[i] = nowX * (B + 1) + nowY;
}
sort(id + 1, id + n + 1);
id[n + 1] = -1;
int now = 1;
int cnt = 0;
int minN = n + 1;
int maxX = 0;
for (int i = 2; i <= n + 1; i++)
{
if (id[i] == id[i - 1])
now++;
else
{
minN = min(minN, now);
maxX = max(maxX, now);
cnt++;
now = 1;
}
}
if (cnt < A * B)
minN = 0;
cout << minN << " " << maxX << "\n";
return 0;
}
初始给定一个包含 个点, 条边的无向图 。
给定 对点对 。如果图保证了这其中的任意一对点对都不连通,我们就说这是一个 good
图。
初始的图 为一个 good
图, 有 个问题:
第 个问题会给两个点 ,问如果给这两个点之间连上边,图 还是不是 good
图。
首先并查集与处理好所有连通块。接下来可以把所有的 个点对抽象为 个连通块对。
每次的询问就是看看 所属的连通块,构成的连通块对,是否在前面抽象出来的那 个连通块对里。
后面这个查询我是直接把 个连通块对分别打包放入了 set
中,然后查询。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int K;
int Q;
int fa[212345];
int findFa(int x)
{
if (x == fa[x])
return x;
return fa[x] = findFa(fa[x]);
}
set<pair<int, int>> s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
int faU = findFa(u);
int faV = findFa(v);
if (faU != faV)
fa[faU] = faV;
}
cin >> K;
for (int i = 1; i <= K; i++)
{
int x, y;
cin >> x >> y;
int faX = findFa(x);
int faY = findFa(y);
if (faX > faY)
swap(faX, faY);
//cout << faX << "," << faY << endl;
s.insert(make_pair(faX, faY));
}
cin >> Q;
while (Q--)
{
int p, q;
cin >> p >> q;
int faP = findFa(p);
int faQ = findFa(q);
if (faP > faQ)
swap(faP, faQ);
//cout << faP << " " << faQ << endl;
if (s.find(make_pair(faP, faQ)) != s.end())
cout << "No\n";
else
cout << "Yes\n";
}
return 0;
}
Taka 和 Aoki 接下来 天在进行兼职。
给出 Taka 的上班时间计划 ,字符串 的第 个字符表示 Taka 的安排,如果是 #
就表示上班,如果是 .
就表示不上班。
Aoki 拿到了 ,就开始规划自己的上班安排了。他是按照下面的步骤规划的:
问 Aoki 有多少种可行的上班计划,能保证 天的每天都至少有一个人上班。答案可能很多,输出对 取余后的结果即可。
首先可以 枚举 的所有因子 。对于每个因子,可以计算对应的上班计划数量。
显然只需要 统计出这 天里,有多少天是可上可不上的。答案就是 的这么多次方。
这样我们就得到了所有的 对应的上班方案数 cnt_m_i,显然这里面是可能会有重复的。
可以从小到大枚举每个循环节 ,把 减去 。这样就保证里每种方案只在最小的循环节里被统计了。
因为是从小到大做,所以对于当前的 来说,所以保证了去掉了所有循环节为 的方案,也就是 里的方案都保证了最小循环节为 。
接下来只需要保证这些方案不在循环节长度超过 时被统计,显然此时有可能的循环节长度只能是 的倍数 ,因此只要 减去 即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int n;
string s;
bool flag[112345];
int cnt[112345]; // cnt[i]:m=i 时有几种排班表
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
int nn = sqrt(n);
for (int i = 1; i <= nn; i++)
{
if (n % i != 0)
continue;
int m = i;
for (int i = 0; i < m; i++)
flag[i] = false;
for (int i = 0; i < n; i++)
{
if (s[i] == '.')
flag[i % m] = true;
}
/*
cout << m << ":\n";
for (int i = 0; i < m; i++)
cout << flag[i];
cout << "\n";
*/
cnt[m] = 1;
for (int i = 0; i < m; i++)
if (!flag[i])
cnt[m] = (cnt[m] * 2) % MOD;
if (i != 1 && i * i != n)
{
m = n / i;
for (int i = 0; i < m; i++)
flag[i] = false;
for (int i = 0; i < n; i++)
{
if (s[i] == '.')
flag[i % m] = true;
}
/*
cout << m << ":\n";
for (int i = 0; i < m; i++)
cout << flag[i];
cout << "\n";
*/
cnt[m] = 1;
for (int i = 0; i < m; i++)
if (!flag[i])
cnt[m] = (cnt[m] * 2) % MOD;
}
}
/*
for (int i = 1; i <= n; i++)
cout << i << ":" << cnt[i] << " ";
cout << endl;
*/
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans = (ans + cnt[i]) % MOD;
if (cnt[i])
for (int j = 2 * i; j <= n; j += i)
{
if (cnt[j])
cnt[j] = (cnt[j] - cnt[i] + MOD) % MOD;
}
}
/*
for (int i = 1; i <= n; i++)
cout << i << ":" << cnt[i] << " ";
cout << endl;
*/
cout << ans << "\n";
return 0;
}
/*
###. ..##
.#.#
*/