[学长的财产] codevs Noip模拟赛1(FFF团的算式/后宫/菊花)

    已退役学长留下的一堆做过的模拟赛中的一套。。。。大概以后会写一个系列

    因为在弱校，教练也不太爱收钱，所以并没有机会买题训练，索性学长留下了丰厚的遗产财产，所以每周挑一套做着玩

    这套题在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

这道题有一个坑点：如果不连通输出-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

我怀疑这题和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;
}