Educational Codeforces Round 84 (Rated for Div. 2)
https://codeforces.com/contest/1327
将数字 n 分成 k 个互不相等的奇数，首先 n 和 k 对 2 取模要相等，不然不可能分成 k 个奇数，其次考虑 k 个不同的奇数能组成的最小的数字是否大于等于 n 即可
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ll n, k;
sc("%lld%lld", &n, &k);
ll ans = 0;
ans = k * k;
if (n >= ans && n % 2 == k % 2)
pr("YES\n");
else
pr("NO\n");
}
} 就是给你这么多对关系，每次公主选择最前面的国家，如果没有全部嫁出去就随机输出一对
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
bool can1[MAXN], can2[MAXN];
int a[MAXN];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
{
can1[i] = false;
can2[i] = false;
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
int num;
sc("%d", &num);
for (int j = 0; j < num; j++)
sc("%d", &a[j]);
for (int j = 0; j < num; j++)
{
if (can2[a[j]] == false)
{
can1[i] = true;
can2[a[j]] = true;
cnt++;
break;
}
}
}
if (cnt == n)
{
pr("OPTIMAL\n");
}
else
{
pr("IMPROVE\n");
for (int i = 1; i <= n; i++)
{
if (can1[i] == false)
{
pr("%d", i);
break;
}
}
pr(" ");
for (int i = 1; i <= n; i++)
{
if (can2[i] == false)
{
pr("%d", i);
break;
}
}
pr("\n");
}
}
} 将他全部放到角落的格子里，然后遍历全图
这个方向和正常的坐标系方向不一样，注意输出。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int main()
{
int n, m;
sc("%d%d", &n, &m);
if (n == 1 && m == 1)
pr("0");
else if (n == 1)
{
pr("%d\n", 2 * m - 2);
for (int i = 1; i < m; i++)
pr("R");
for (int i = 1; i < m; i++)
pr("L");
}
else if (m == 1)
{
pr("%d\n", 2 * n - 2);
for (int i = 1; i < n; i++)
pr("D");
for (int i = 1; i < n; i++)
pr("U");
}
else
{
pr("%d\n", n + m - 2 + n * m - 1);
for (int i = 1; i < n; i++)
pr("U");
for (int i = 1; i < m; i++)
pr("R");
for (int i = m; i >= 1; i--)
{
for (int j = 1; j < n; j++)
{
if (i % 2 == m % 2)
pr("D");
else
pr("U");
}
if (i != 1)
pr("L");
}
}
} 
并且我们仔细看每个环在输入的全排列中的位置。
所以结论就是你只要找到一个环，枚举他的因子，然后去判断，相隔因子位置的那些数字颜色是否相等，即可。
预处理每个数字的因子
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int p[MAXN], c[MAXN];
bool book[MAXN];
int ans;
vector<int>d[MAXN];
void calc(vector<int>v)
{
int sz = v.size();
for (auto i : d[sz])
{
for (int j = 0; j < i; j++)
{
for (int k = j; k < sz; k += i)
{
if (c[v[j]] != c[v[k]])
goto qwe;
}
ans = min(ans, i);
qwe:;
}
}
}
int main()
{
for (int i = 1; i <= 2e5; i++)
for (int j = i; j <= 2e5; j += i)
d[j].push_back(i);
int T;
sc("%d", &T);
while (T--)
{
ans = 1e6;
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
book[i] = false;
for (int i = 1; i <= n; i++)
sc("%d", &p[i]);
for (int i = 1; i <= n; i++)
sc("%d", &c[i]);
for (int i = 1; i <= n; i++)
{
if (book[i] == false)
{
vector<int>v;
int t = i;
while (book[t] == false)
{
book[t] = true;
v.push_back(t);
t = p[t];
}
calc(v);
}
}
pr("%d\n", ans);
}
} 先打个表
10
180 10
2610 180 10
34200 2610 180 10
423000 34200 2610 180 10
看起来感觉很有规律，反过来看一下 n=5 的情况
10 180 2610 34200 423000
求一个前缀和（以下都是乱搞）
10 190 2800 37000 46000
再求一个前缀和
10 200 3000 40000 50000
所以先打个表求出前缀和的前缀和，然后脱两次前缀和即可。
#include <bits/stdc++.h> #define ll long long #define sc scanf #define pr printf using namespace std; ll ten[200005]; ll t1[200005]; ll t2[200005]; ll ans[200005]; const ll mod = 998244353; int main() { int n; sc("%d", &n); ten[0] = 1; for (int i = 1; i <= n; i++) ten[i] = ten[i - 1] * 10 % mod; for (int i = 1; i <= n; i++) t1[i] = i * ten[i] % mod; for (int i = 1; i <= n; i++) t2[i] = (t1[i] - t1[i - 1] + mod) % mod; for (int i = 1; i <= n; i++) ans[i] = (t2[i] - t2[i - 1] + mod) % mod; for (int i = n; i >= 1; i--) pr("%lld%c", ans[i], i == 1 ? '\n' : ' '); }
打表代码：
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int cnt[10];
int main()
{
string s;
for (int i = 1; i <= 5; i++)
{
memset(cnt, 0, sizeof(cnt));
int now = 0;
int num = pow(10, i) - 1;
while (now <= num)
{
s = to_string(now);
while (s.size() < i)
s = "0" + s;
now++;
int f = 1;
for (int j = 1; j < s.size(); j++)
{
if (s[j] == s[j - 1])
f++;
else
{
if (f <= i)
cnt[f]++;
else
{
cout << " ";
}
f = 1;
}
}
cnt[f]++;
}
for (int j = 1; j <= i; j++)
pr("%d%c", cnt[j], j == i ? '\n' : ' ');
}
}
投递谷歌等公司10个岗位 >
