已退役学长留下的一堆做过的模拟赛中的一套。。。。大概以后会写一个系列
因为在弱校，教练也不太爱收钱，所以并没有机会买题训练，索性学长留下了丰厚的遗产财产，所以每周挑一套做着玩
这套题在codevs上搜索FFF就可以找到，但是T1的题面出了一点问题，所以手动上传一波：
原题链接：A
这道题的核心在于欧拉函数以及化简
首先你要知道f(n)就是求n的欧拉函数，下文写作phi(n)
化简部分略长，手写图片希望不要被嫌弃
emmmmmm，所以，经过如上步骤……我们成功将这个算式化简到了不那么难的地步，phi直接用定义式算，另一部分dfs构造即可
#include <bits/stdc++.h>
#define LL long longusing std::min;
using std::max;
using std::swap;
using std::sort;
using std::set;const int MAXN = 1001;
const LL INF = 0x7FFFFFFFFFF;#define Debug(...) fprintf(stderr, __VA_ARGS__)template <typename T> inline void read(T &x) {int c = getchar();bool f = false;for (x = 0; !isdigit(c); c = getchar()) {if (c == '-') {f = true;}}for (; isdigit(c); c = getchar()) {x = x * 10 + c - '0';}if (f) {x = -x;}
}LL N, Phi, P[MAXN];
set<LL>r;
int cnt, tot;LL phi(LL n) { LL ret = 1, i; for(i = 2; i * i <= n; i++) { if(n % i == 0) { P[++cnt] = i;n /= i; ret *= i - 1; while(n % i == 0) { n /= i; ret *= i;P[++cnt] = i;} } } if(n > 1) ret *= (n - 1), P[++cnt] = n; return ret;
} void calc(bool fg, int x, LL now) {if(x == cnt) {if(!fg) return;else {now *= P[cnt];r.insert(now);return ;}}if(fg) now *= P[x];r.insert(now);calc(0, x + 1, now);calc(1, x + 1, now);
}signed main() {read(N);LL ans = phi(N);calc(0, 0, 1);set<LL>::iterator it; LL ret = 0;for(it = r.begin(); it != r.end(); it++)ret += phi(N / (*it)) * (*it);printf("%lld\n", ans + ret % N);return 0;
}原题：B
你在某日收到了 FFF 团卧底的求助,在他某日旅游回来,他的后宫们出现了一些不可调和的矛盾,如果 FFF 团卧底把自己的宝贝分给 a 号妹子,那么 b 号妹子至少要在站在 a 号妹子的右边距离 d,妹子才愿意得到那个宝贝。可是后宫里也有玩得好的妹子呀,她们总是渴望亲近一点,如果把自己的宝贝分给 a 号妹子,那么与她亲近的妹子与 a 号妹子的距离不会超过 l。现在总共有 n 个妹子,k 个这样的矛盾关系,m 个亲近关系。假设他的宝贝是无限的,保证每一个妹子都有宝贝的情况下,第 n 个妹子和第一个妹子的最远距离是多少呢?
第一行为 n,m,k
此后 m 行为亲近关系
此后 k 行为矛盾关系
一行,为最长的距离
4 2 1
1 3 100
2 4 200
2 3 33
267
对于 40%的数据,n<=100
对于 100%的数据,n<=1000,m<=10000,从 1 开始编号,距离在 int 范围内
这道题有一个坑点：如果不连通输出-2，无解输出-1
题面没说！！！！
尴尬……
但是其实就是一道简单的差分约束板题，详情请见代码
#include <bits/stdc++.h>using std::min;
using std::max;
using std::swap;
using std::sort;
using std::queue;const int MAXN = 100100;
const int MAXE = 400400;
const int INF = 0x3f3f3f3f;#define Debug(...) fprintf(stderr, __VA_ARGS__)
//#define getchar() *S ++
//char RR[3 * 1024 * 1024], *S = RR;template <typename T> inline void read(T &x) {int c = getchar();bool f = false;for (x = 0; !isdigit(c); c = getchar()) {if (c == '-') {f = true;}}for (; isdigit(c); c = getchar()) {x = x * 10 + c - '0';}if (f) {x = -x;}
}struct Edge {int to, nxt, len;Edge() {}Edge(int _to, int _nxt, int _len) : to(_to), nxt(_nxt), len(_len){}
}E[MAXE];int p, h[MAXN], vis[MAXN], d[MAXN], sum[MAXN];
int n, m, k;queue<int>q;inline void add_edge(int u, int v, int w) {E[++p] = Edge(v, h[u], w), h[u] = p;//E[++p] = Edge(u, h[v], -w), h[v] = p;
}inline int SPFA(int x) {memset(d, 0x3f, sizeof(d));memset(vis, 0, sizeof(vis));vis[x] = 1; d[x] = 0;sum[x] = 0;q.push(x);while(!q.empty()) {int u = q.front(); q.pop();vis[u] = 0;for(int i = h[u]; i; i = E[i].nxt) {int v = E[i].to;if(d[v] > d[u] + E[i].len) {d[v] = d[u] + E[i].len;sum[v] = sum[u] + 1;if(sum[v] >= n) return -1;if(!vis[v]) {vis[v] = 1;q.push(v);}}}}return d[n] == INF ? -2 : d[n];
}signed main() {read(n), read(m), read(k);for(int i = 1, a, b, c; i <= m; i++) {read(a), read(b), read(c);add_edge(a, b, c);}for(int i = 1, a, b, c; i <= k; i++) {read(a), read(b), read(c);add_edge(b, a, -c);}printf("%d\n", SPFA(1));return 0;
} 原题：C
FFF 团卧底在这次出题后就知道他的菊花可能有巨大的危险,于是他提前摆布好了菊花阵,现在菊花阵里有若干朵菊花,出现次数最多的那一朵就是出题人的,你的任务是需要找出出题人的菊花。
第一行为 n
第二行为 n 朵菊花
一行,为出题人的菊花
5
1 1 1 2 3
1
对于 100%的数据,n<=5000000,每个数都在 int 范围内,保证出题人的菊花出现的次数大于等于[n/2]
我怀疑这题和A题搞反了。。。
不解释
#include <bits/stdc++.h>signed main() {int n, m, cnt = 0, num = 0;scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d", &m);if(cnt == 0) {cnt = 1;num = m;continue;}if(m == num) cnt++;else cnt--;}printf("%d\n", num);return 0;
}