A.Kuroni and the Gifts
题意：给定两个数字序列a、b，问怎么排使得每一个i对应的ai+bi都不同。（保证原本两个数组内不存在相同元素）
题解：全部从小到大排序即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
int a[maxn],b[maxn];
void solve()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
sort(a,a+n);
sort(b,b+n);
for(int i=0;i<n;i++)
printf("%d ",a[i]);
puts("");
for(int i=0;i<n;i++)
printf("%d ",b[i]);
puts("");
}
int main()
{
int t;
for(scanf("%d",&t);t>=1;t--)
solve();
}B.Kuroni and Simple Strings
题意：规定一个长度为2n的串当且仅当前n个为'('且后n个为')'时为完美串。现给一个串，从中取出子序列，当且仅当子序列为完美串时可删除。问最少删几次可以使得串不可删。
题解：贪心、从左向右找左括号，从右向左找右括号尽量匹配即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> v;
string s;
cin >> s;
int l = 0, r = s.length() - 1;
while (1)
{
while (s[l] != '(' && l < s.length() - 1)
l++;
while (s[r] != ')' && r > 0)
r--;
if (r <= l)
break;
v.push_back(l);
v.push_back(r);
l++, r--;
}
if (v.size() == 0)
{
puts("0");
return 0;
}
puts("1");
printf("%d\n", v.size());
sort(v.begin(), v.end());
for (auto i : v)
printf("%d ", i + 1);
puts("");
return 0;
}C.Kuroni and Impossible Calculation（容斥）
题意：求
对m取模。（m<1000）
题解：
考虑两种情况：
（1）n≤m：暴力。
（2）n>m：答案为0.
证明：所有数对m取模仅有m中取值。若n>m，则一定有两个数对m同余，相减可以被整除。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
ll a[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
if (n > m)
{
puts("0");
return 0;
}
ll ans = 1;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
ans = (ans * abs(a[i] - a[j])) % m;
printf("%lld\n", ans);
return 0;
}D.Kuroni and the Celebration
题意：交互题，每次查询可以得到两个点的LCA。让你保证在n/2次查询内查到根节点。
题解：每次选两个叶节点，对于得出的结果如果为其中一个节点，那么它一定为根，反之删除这两个节点，重新选择任意两个叶节点。一定可以在规定次数内找到
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
bool vis[maxn];
vector<int> G[maxn];
int deg[maxn];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
deg[u]++;
deg[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++)
if (deg[i] == 1)
q.push(i);
for (int k = 1; k <= n / 2; k++)
{
int x = q.front();
q.pop();
int y = q.front();
q.pop();
printf("? %d %d\n", x, y);
cout.flush();
int u;
scanf("%d", &u);
if (u == x || u == y)
{
printf("! %d\n", u);
return 0;
}
vis[x] = 1;
for (auto v : G[x])
{
if (!vis[v])
{
deg[v]--;
if (deg[v] == 1)
q.push(v);
}
}
vis[y] = 1;
for (auto v : G[y])
{
if (!vis[v])
{
deg[v]--;
if (deg[v] == 1)
q.push(v);
}
}
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
printf("! %d\n", i);
return 0;
}
}
return 0;
}E.Kuroni and the Score Distribution（构造）
题意：安排n个严格递增的分数使得
的组数恰好为m组
题解：对于i个数字当且仅当ai=i时可以获得的三元组最多，为(i-1)/2从0到i求和。所以m依次减去贡献直到不可减。关键是怎么根据剩余的m构造出第i个数。后面随便取就行了。具体实现看代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5005;
int a[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int i;
for (i = 1; i <= n; i++)
{
a[i] = i;
if (m < (i - 1) / 2)
break;
m -= (i - 1) / 2;
}
if (i > n && m)
{
puts("-1");
return 0;
}
a[i] = a[i - 1] + a[i - 2] + 2 - 2 * m;
for (++i; i <= n; i++)
a[i] = i * 10000 + 77777777;
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
puts("");
return 0;
}F.Kuroni and the Punishment
题意：给定一个n个数的数组，每次操作可以使其中一个数字加一或者减一。问最少几次操作可以使所有数字的gcd不为1
题解：首先理论最大答案为n。因为可以取2为gcd，后面只要把所有数字变成偶数即可。然后随机排列一下，对每个数字的-1到+1范围内取素因子，然后对每个素因子扫描一下所有数字至少增加次数，求和取最小值即可。（感觉这道题有点搞）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5 + 5;
int n;
ll a[maxn], ans;
vector<ll> fact(ll x)
{
vector<ll> pf;
for (ll i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
while (x % i == 0)
x /= i;
pf.push_back(i);
}
}
if (x != 1)
pf.push_back(x);
return pf;
}
void upd(ll x)
{
ll res = 0;
for (int i = 0; i < n; i++)
{
if (a[i] < x)
{
res += x - a[i];
continue;
}
ll r = a[i] % x;
res += min(r, x - r);
}
ans = min(ans, res);
}
void test(ll x)
{
vector<ll> pf = fact(x);
for (auto p : pf)
upd(p);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%lld", &a[i]);
shuffle(a, a + n, mt);
ans = n;
for (int i = 0; i < min(n, 40); i++)
{
test(a[i]);
if (a[i] > 1)
test(a[i] - 1);
test(a[i] + 1);
}
printf("%lld\n", ans);
return 0;
}
京公网安备 11010502036488号