ZROI 2022CSP7连测 Round6 解题报告
100 + 100 + 0 + 60, rk 23
被学弟爆踩了捏。
A
傻呗数学结论题。
考虑对称轴的性质,我们只需要考虑右半边的即可。
那么显然就是让我们找一个最小的
直接算即可。
void solve() {
ll n,m;read(n,m);
ll ans = 180 * m / __gcd(180 * m,n) - 2;
printf("%lld\n",ans);
}
B
考虑这个加法可以如下实现:
n = 1 << n;
int add(int x,int y) {
x += y;
while (x & n) x ^= n,++x;
return x;
}
然后乘法实际上就是暴力相加,就做完了。
注意 IO 速度即可,时间复杂度
const int N = 5e3 + 10;
int n,t,ans[N][N];
int add(int x,int y) {
x += y;
while (x & n) x ^= n,++x;
return x;
}
inline void writ(int x) {
//if (!x) return ;
if (x >= 10) writ(x/10);
putchar(x % 10 + '0');
}
signed main() {
//FO(inp)
read(t);n = 1 << t;
//printf("%d\n",((1 << (t)) - 1));
for (int i = 0;i < n;++i) putchar('0'),putchar(' ');
puts("");
for (int i = 1;i < n;++i) {
//int i = 2;
int now = 0;
putchar('0'),putchar(' ');
for (int j = 1;j < n;++j) {
now = add(now,i);
writ(now);putchar(' ');
}
puts("");
}
return 0;
}
C
人类智慧博弈题!暂时搁置。
D
我们先用一个经典 trick,一般这种置换都是需要我们先在
接下来我们考虑,这个求
本题的第二部分在于,我们需要把每个
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define int ll
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const ll mod = 998244353;
const double eps = 1e-10;
const int N = 2e6 + 10;
const ll lim = 1e15;
int n,dfn[N],c[N],cnt,siz[N],num,a[N],ans[N],len,M[N],mo[N],p10[N];
ll m,maxx;
char s[N];
int st[N],top;
bool ins[N];
vector <int> G[N],poi[N],buc;
void dfs(int x) {
st[++top] = x;dfn[x] = ++cnt;
for (auto y : G[x]) {
if (!dfn[y]) {
dfs(y);
} else {
int p;c[x] = ++num;
while (top){
p = st[top--];c[p] = num;
poi[num].push_back(p);++siz[num];
}
buc.push_back(siz[num]);
reverse(poi[num].begin(),poi[num].end());
}
}
}
signed main() {
read(n);
for (int i = 1;i <= n;++i) read(a[i]),G[i].push_back(a[i]);
for (int i = 1;i <= n;++i) if (!dfn[i]) dfs(i);
scanf("%s",s+1);
len = strlen(s + 1);
sort(buc.begin(),buc.end());
buc.erase(unique(buc.begin(),buc.end()),buc.end());
p10[0] = 1;
for (int i = 1;i <= 12;++i) p10[i] = p10[i-1] * 10;
for (int l = 1,r = 1;l <= len;l = r + 1) {
r = min(l + 11,len);
ll tmp = 0;
for (int j = l;j <= r;++j) tmp = tmp * 10 + s[j] - '0';
for (auto x : buc) M[x] = (M[x] * p10[r-l+1] + tmp) % x;
}
for (int j = 1;j <= n;++j) {
for (ll k = 0;k < siz[j];++k) {
m = M[siz[j]];
ans[poi[j][k]] = poi[j][(k + m) % siz[j]];
}
}
for (int i = 1;i <= n;++i) printf("%lld ",ans[i]);
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
B的加法可以O(1)吧?
qs 我当时好像写挂了就换了个稍微靠谱点的做法