JYOI 11.19 膜你赛
T1
20pts
枚举全排列即可（也是我这个蒟蒻的考场做法……）
时间复杂度 \(O(kn \times n!)\)
#include <bits/stdc++.h>
#define int long long
#define maxn 105
const int inf = 1e9;
using namespace std;
inline int read(){
int x = 0 , f = 1 ; char c = getchar() ;
while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
return x * f ;
}
int n, k, p;
int tmp[maxn], a[maxn], ans;
bool calc(int x) {
for (int i = 1; i <= x; i++) {
int tt[20] = {0};
for (int j = 1; j <= n; j++)
tt[j] = tmp[tmp[j]];
for (int j = 1; j <= n; j++) tmp[j] = tt[j];
}
bool flag = 1;
for (int i = 1; i <= n; i++) if (tmp[i] != i) flag = 0;
return flag;
}
signed main() {
freopen("perm.in", "r", stdin);
freopen("perm.out", "w", stdout);
n = read(), k = read(), p = read();
for (int i = 1; i <= n; i++) a[i] = i;
do{
for (int i = 1; i <= n; i++) tmp[i] = a[i];
if (calc(k)) ans++;
}while (next_permutation(a + 1, a + n + 1));
cout << ans % p;
}
40pts
考虑骗 \(k =1\) 的分。
对于 \(k = 1\) 的情况时，这个原序列必须要么是 \(p_i = i\)，要么是 \(p_{p_i} = i\)，我们可以设计一个 DP：
设 \(f[n]\) 表示长度为 \(n\) 时的方案数。考虑一下怎么转移：首先，若是 \(p_n = n\)，那么只将 \(f[n - 1]\)转移过来；还有另一种情况是 \(p_n \ne n\)，\(p_n\) 为除了 \(n\) 之外的 \(n - 1\) 种可能，此时，\(n\) 不在本位，那么可以通过观察发现此时的 \(p_n\) 可以决定两个数了，所以对于任何一种情况，方案数都要加 \(f[n - 2]\)。
故状态转移方程为 \(f[n] = f[n - 1] + (n - 1) \times f[n - 2]\)。
60pts
80pts
100pts
++了我都不会呀看了题解也不会
T2
60/80pts
用 \(lcm\) 优化一下，按说只能得60，但是xiaobu的样例出了点问题能得80……
#include <bits/stdc++.h>
#define int long long
#define maxn 1000005
#define inf 1e9
using namespace std;
inline int read(){
int x = 0 , f = 1 ; char c = getchar() ;
while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
return x * f ;
}
int n, m, k, a[maxn], b[maxn];
signed main() {
freopen("period.in", "r", stdin);
freopen("preiod.out", "w", stdout);
n = read(), m = read(), k = read();
for (int i = 0; i < n; i++) a[i] = read();
for (int i = 0; i < m; i++) b[i] = read();
int ans = 0, kans = 0;
int tmp = __gcd(n, m);
int kk = tmp * (n / tmp) * (m / tmp);
if (k < kk) {
for (int i = 0; i < k; i++)
if (a[i % n] < b[i % m]) ans++;
cout << ans << endl;
}
else {
for (int i = 0; i < kk; i++)
if (a[i % n] < b[i % m]) kans++;
for (int i = 0; i < k - (k / kk) * kk; i++)
if (a[i % n] < b[i % m]) ans++;
ans += (k / kk) * kans;
cout << ans;
}
}
100pts
T3
最简单的一道题……然而我手贱，得分还不如暴力……
？~ ？pts
写了个退火……（我个sb
一开始还没读懂题，看见有几个里面选的格式，就想到了退火经典模型，再想到T3应该挺难的正解应该无望，于是开始退火……
RP好像还不怎么行，测试前面几个点也有WA的。
#include <bits/stdc++.h>
#define int long long
#define maxn 1000005
const int inf = 1e9;
using namespace std;
inline int read(){
int x = 0 , f = 1 ; char c = getchar() ;
while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
return x * f ;
}
int n, m, k;
struct edge{
int u, v, w;
}e[maxn], e2[maxn];
bool cmp(edge a, edge b) {
return a.w < b.w;
}
vector<int> can, nt;
int Ans, f[maxn], pd[maxn];
int find(register int x) {
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
int tot, flag;
int calc() {
int now = 0;
for (register int i = 1; i <= n; i++) f[i] = i;
for (register int i = 0; i < can.size(); i++) {
int u = e[can[i]].u, v = e[can[i]].v;
if (find(u) == find(v)) return inf;
f[find(u)] = find(v);
now = max(now, e[can[i]].w);
}
for (register int i = 1; i <= tot; i++) {
int u = e2[i].u, v = e2[i].v;
int x = find(u), y = find(v);
if (x == y) continue;
now = max(now, e2[i].w);
f[x] = y;
}
return now;
}
int tt = 0;
vector<int> tmp;
void SA() {
for (double T = 1000; T > 1e-5; T *= 0.9976) {
int x = rand() % k, y = rand() % (tt - k);
swap(can[x], nt[y]);
int now = calc();
int del = now - Ans;
if (del < 0) Ans = now;
else if (exp(-del / T) * RAND_MAX <= rand())
swap(can[x], nt[y]);
}
}
signed main() {
srand(time(0));
n = read(), m = read(), k = read();
for (register int i = 1; i <= m; i++) {
e[i].u = read(), e[i].v = read(), e[i].w = read();
int opt = read();
if (!opt) {
if (tt < k) can.push_back(i);
else nt.push_back(i);
tt++;
pd[i] = 1;
}
}
for (register int i = 1; i <= m; i++) if (!pd[i]) e2[++tot] = e[i];
sort(e2 + 1, e2 + tot + 1, cmp);
Ans = calc();
while ((double)clock() / CLOCKS_PER_SEC < 0.75) SA();
cout << Ans;
}
eee
100pts
二分啊啊啊啊啊啊
既然是最大值最小, 当然是考虑二分。
二分答案之后, 还需要知道用这些边能不能造出一个恰有 \(
标签：11.19,int,getchar,fa,while,include,define From： https://www.cnblogs.com/Echo-djc/p/16908960.html