[CF 965E]Short Code
你有\(n\)个两两不同的串，你要将每个串变成其的一个前缀，使得变换后的所有串仍然两两不同，并且所有串长度和尽可能小，输出这个和。
\(n\leq 10^5\)，所有串长之和不超过\(10^5\)。
[CF 900F]Unusual Sequence
求有多少正整数序列，满足所有数的最大公约数为\(x\)，所有数的和为\(y\)。
\(1\leq x, y\leq 10^9\)。
[CF 438E]The Child and Binary Tree
给你一个大小为\(n\)的集合\({c_1, c_2,\ldots ,c_n}\)，规定合法的二叉树为带点权且点权都属于给定集合中的点的数。对于任意整数$i\in [1, m]$，求出有多少不同的点权和为\(i\)的二叉树并输出之。
\(1\leq n, m, c_i\leq 10^5\)。
[CF 1000F]One Occurrence
好前一段时间因为一些神必原因……博客放到了https://yahyachan.github.io。然后因为我回学校了所以接下来很长时间可能会继续用这个博客？
我谔谔，还是说这题……
对于询问\([l, r]\)，考虑所有数在其中第一次出现的位置，如果说这个数在整个区间里只出现了一次，那么这个数下一次出现的位置一定大于\(r\)。
因此我们用扫描线搞一下就好啦……
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using pii = std::pair<int, int>;
const int maxn = 500005;
const int maxno = maxn << 2;
pii maxv[maxno];
void maintain(int o) {
maxv[o] = std::max(maxv[o << 1], maxv[o << 1 | 1]);
}
void build_tree(int o, int L, int R) {
if(L == R) {
maxv[o] = std::make_pair(-1, -1);
} else {
int M = (L + R) / 2;
build_tree(o << 1, L, M);
build_tree(o << 1 | 1, M + 1, R);
maintain(o);
}
}
void modify(int o, int L, int R, const int &p, const pii &v) {
if(L == R) {
maxv[o] = v;
} else {
int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o);
}
}
pii query(int o, int L, int R, const int &ql, const int &qr) {
if(ql <= L && R <= qr) {
return maxv[o];
} else {
int M = (L + R) / 2;
pii ret = std::make_pair(-100, -100);
if(ql <= M) ret = std::max(ret, query(o << 1, L, M, ql, qr));
if(qr > M) ret = std::max(ret, query(o << 1 | 1, M + 1, R, ql, qr));
return ret;
}
}
int rec[maxn], next[maxn];
int A[maxn];
std::vector<pii> que[maxn]; int ans[maxn];
int main() {
int n; scanf("%d", &n);
std::fill(rec, rec + maxn, n + 1);
for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
for(int i = n; i >= 1; i --) {
next[i] = rec[A[i]];
rec[A[i]] = i;
}
int q; scanf("%d", &q);
for(int i = 1; i <= q; i ++) {
int l, r; scanf("%d%d", &l, &r);
que[l].push_back({r, i});
}
build_tree(1, 1, n);
for(int i = 1; i <= 500000; i ++) {
if(rec[i] <= n) {
modify(1, 1, n, rec[i], {next[rec[i]], i});
}
}
for(int i = 1; i <= n; i ++) {
for(const pii &g : que[i]) {
int r = g.first, id = g.second;
pii tmp = query(1, 1, n, i, r);
if(tmp.first <= r) {
ans[id] = 0;
} else {
ans[id] = tmp.second;
}
}
int nx = next[i];
if(nx <= n) {
modify(1, 1, n, nx, {next[nx], A[i]});
}
}
for(int i = 1; i <= q; i ++) {
printf("%d\n", ans[i]);
}
return 0;
}
[CF 618F]Double Knapsack
我zzs就算掉光rating，R2爆炸，也不会做你们半道构造题！
啊构造题真好玩（一转）。
不妨钦定\(A\)中所有元素的和不大于\(B\)的。然后把两个集合按照任意顺序搞成一个序列，然后求出两者的前缀和\(SA\)和\(SB\)。
考虑对于0...n的\(SA_i\)，找出\(SB\)中不大于他的数中最大的一个（不妨设为\(SB_j\)），可以发现有\(0\leq SA_i - SB_j\leq n - 1\)（不然\(j\)还能再大）。然后发现：我们处理的\(i\)和\(j\)的数对有\(n + 1\)组，但是\(SA_i - SB_j\)的取值却只有N种！也就是说一定存在\(i\neq i'\)且\(j\neq j'\)满足\(SA_i - SB_j = SA_{i'} - SB_{j'}\)。
我们找出两对这样的数对，移一下项就可以构造一组解了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
using pii = std::pair<int, int>;
int n;
void gen_S(int *arr, ll *S) {
S[0] = 0LL;
for(int i = 1; i <= n; i ++) {
S[i] = (S[i - 1] + (ll(arr[i])));
}
}
const int maxn = 1000005;
std::vector<pii> cs[maxn];
int main() {
scanf("%d", &n);
int *A = (int*)calloc(n + 1, sizeof(int));
int *B = (int*)calloc(n + 1, sizeof(int));
ll sum_A = 0LL, sum_B = 0LL;
for(int i = 1; i <= n; i ++) {
scanf("%d", &A[i]); sum_A += A[i];
}
for(int i = 1; i <= n; i ++) {
scanf("%d", &B[i]); sum_B += B[i];
}
bool flip = false;
if(sum_A > sum_B) {
flip = true;
std::swap(A, B);
std::swap(sum_A, sum_B);
}
ll *SA = (ll*)calloc(n + 1, sizeof(ll));;
ll *SB = (ll*)calloc(n + 1, sizeof(ll));;
gen_S(A, SA); gen_S(B, SB);
for(int i = 0; i <= n; i ++) {
int j = std::upper_bound(SB, SB + n + 1, SA[i]) - SB - 1;
ll val = SA[i] - SB[j];
cs[val].push_back(std::make_pair(i, j));
}
int l1, r1, l2, r2;
for(int i = 0; i < n; i ++) {
if(cs[i].size() > 1) {
int i1 = cs[i][0].first;
int j1 = cs[i][0].second;
int i2 = cs[i][1].first;
int j2 = cs[i][1].second;
if(i1 > i2) {
std::swap(i1, i2);
std::swap(j1, j2);
}
l1 = i1; r1 = i2;
l2 = j1; r2 = j2;
break;
}
}
if(flip) {
std::swap(l1, l2);
std::swap(r1, r2);
}
printf("%d\n", r1 - l1);
for(int i = l1 + 1; i <= r1; i ++) {
if(i > l1 + 1) putchar(' ');
printf("%d", i);
}
putchar('\n');
printf("%d\n", r2 - l2);
for(int i = l2 + 1; i <= r2; i ++) {
if(i > l2 + 1) putchar(' ');
printf("%d", i);
}
putchar('\n');
free(A); free(B);
free(SA); free(SB);
return 0;
}
[CF 19E]Fairy
啊啊啊我只会做水题了……
这题就是要求你只删除一条边拆爆所有的奇环，同时不能产生新的gay环，求所有可能的选择方案。
如果说只有一个奇环，那么上面的树边和非树边都是可以拆爆的。但如果有好几个奇环，那么只能选择树边了。奇环的树边部分肯定是若干链，我们只要树上差分标记一下就能求出这些链的交了。
但考虑一件事，如果一个偶环和一个奇环的树边部分相交了，那么删掉其中一边会导致新的奇环出现（证明的话考虑将环异或一下）。所以说在偶环的树边并上的边也不能取。
注意这题图可能不连通……所以要对每个连通块都DFS。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using ll = long long;
const int maxn = 10005;
const int maxm = 20005;
struct Edge {
int u, v;
int id;
};
std::vector<Edge> G[maxn];
int n, m;
inline void ins_edge(int u, int v, int id) {
G[u].push_back((Edge){u, v, id});
G[v].push_back((Edge){v, u, id});
}
int dep[maxn], anc[maxn][15];
bool vis[maxn];
void dfs_1(int x, int fa = -1) {
vis[x] = true;
anc[x][0] = fa;
for(auto &e : G[x]) {
int v = e.v;
if(!vis[v]) {
dep[v] = dep[x] + 1;
dfs_1(v, x);
}
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) std::swap(u, v);
for(int j = 14; j >= 0; j --) {
int a = anc[u][j];
if(a != -1 && dep[a] >= dep[v]) u = a;
}
if(u == v) return u;
for(int j = 14; j >= 0; j --) {
int a1 = anc[u][j];
int a2 = anc[v][j];
if(a1 != -1 && a2 != -1 && a1 != a2) {
u = a1, v = a2;
}
}
return anc[u][0];
}
bool used[maxm];
int d1[maxn], d2[maxn];
int o_cnt = 0, o_id;
void dfs_2(int x) {
vis[x] = true;
for(auto &e : G[x]) {
if(used[e.id]) continue;
used[e.id] = true;
int v = e.v;
if(vis[v]) {
int l = lca(x, v);
int dis = dep[x] + dep[v] - 2 * dep[l];
int *d;
if(dis & 1) {
d = d2;
} else {
d = d1;
o_cnt ++;
if(o_cnt == 1) o_id = e.id;
}
d[x] ++; d[v] ++; d[l] -= 2;
} else {
dfs_2(v);
}
}
}
void dfs_3(int x) {
vis[x] = true;
for(auto &e : G[x]) {
int v = e.v;
if(!vis[v]) {
dfs_3(v);
d1[x] += d1[v];
d2[x] += d2[v];
}
}
}
bool allow[maxm], expc[maxm];
void dfs_4(int x) {
vis[x] = true;
for(auto &e : G[x]) {
int v = e.v, id = e.id;
if(!vis[v]) {
if(d1[v] == o_cnt) {
allow[id] = true;
}
if(d2[v] > 0) {
expc[id] = true;
}
dfs_4(v);
}
}
}
std::vector<int> ret;
void solve() {
memset(anc, -1, sizeof(anc));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_1(i);
}
for(int j = 1; (1 << j) < n; j ++) {
for(int i = 1; i <= n; i ++) {
int a = anc[i][j - 1];
if(a != -1) {
anc[i][j] = anc[a][j - 1];
}
}
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_2(i);
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_3(i);
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_4(i);
}
if(o_cnt == 0) {
for(int i = 1; i <= m; i ++) ret.push_back(i);
} else {
for(int i = 1; i <= m; i ++) {
if(allow[i] && (!expc[i])) {
ret.push_back(i);
} else if(o_cnt == 1 && o_id == i) {
ret.push_back(i);
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v);
ins_edge(u, v, i);
}
solve();
printf("%d\n", ret.size());
bool flag = false;
for(auto i : ret) {
if(flag) putchar(' ');
flag = true;
printf("%d", i);
}
puts("");
return 0;
}
[CF 711D]Directed Roads
这个题啊……其实不难。
首先你注意，他告诉你你可以把边弄反。
其次注意，这个图不一定就有一个环。
然后每个环的取反法有[tex]2^x[/tex]种（假设环中有[tex]x[/tex]条边），但是空集不行，全集也不行，因此每个环爆掉的方案有[tex]2^x-2[/tex]种。然后环之外的边随便弄，乘法原理乱搞即可。
然后你是不是感觉这个题似曾相识？是的似乎这个题就是NOIP D1T2的翻版。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=200001;
const ll MOD=1000000007;
int G[maxn];
int in[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
register int i;
bool ans=false;
for(i=1;i<=n;i++){
if(!vis[i] && !in[i]){
ans=true;
in[G[i]]--;
vis[i]=true;
G[i]=0;
}
}
return ans;
}
ll dfs(int x,int y){
if(x==y && vis[x]){
return 0;
}else{
vis[x]=true;
return dfs(G[x],y)+1;
}
}
ll pow_mod(ll a,ll b){
if(!b){
return 1;
}else{
ll ans=pow_mod(a,b/2);
ans=ans*ans%MOD;
if(1&b){
ans=(ans*(a%MOD))%MOD;
}
return ans;
}
}
inline ll solve(){
register int i;
register ll Huan,temp=0,ans=1;
while(jianz());
for(i=1;i<=n;i++)
if(!vis[i]){
Huan=dfs(i,i);
temp+=Huan;
ans=(ans*(pow_mod(2,Huan)+MOD-2))%MOD;
}
ans=(ans*pow_mod(2,n-temp))%MOD;
return ans;
}
int main(){
register int i;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&G[i]);
in[G[i]]++;
}
printf("%I64d\n",solve());
return 0;
}
[CF 710E]Generate a String
很不错的题。
很容易想到大爆搜：每搜索一个点，预处理只插入的深度，然后限制之。之后再加一些其他的剪枝。不过估计会炸。
然后有同学就想：那个删除操作真特么棘手啊……因为这个就用不了DP了……哎
不过，删除的目的是什么？下一步干啥？再插入？那就有病了。肯定是要复制。所以说我们可以想出如下状态转移方程（i11r的TeX插件好像不能排版多行公式，所以分两部分写吧）：
[tex]i[/tex]为偶数时[tex]f[i]=min(f[i-1]+x,f[i/2]+y)[/tex]
[tex]i[/tex]为奇数时[tex]f[i]=min(f[i-1]+x,f[(i+1)/2]+x+y)[/tex]
然后问题就迎刃而解了。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e7+2;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
ll d[maxn];
int main(){
ll n,x,y;
cin>>n>>x>>y;
register ll i;
d[0]=0;
REP(i,n+1)
d[i]=x*i;
REP(i,n){
if(1&i){
d[i]=min(d[i-1]+x,d[(i+1)/2]+x+y);
}else{
d[i]=min(d[i-1]+x,d[i>>1]+y);
}
}
cout<<d[n]<<endl;
return 0;
}
[CF 707C]Pythagorean Triples
很好的数学题啊……
一看就应该想起来构造，对于[tex]n[/tex]为奇数的情况，我们可以假设[tex]n[/tex]为最小数。由此，可以构造出来[tex](n,(n^{2}-1)/2,(n^{2}-1)/2+1)[/tex]一组勾股数（具体证明自己证去）。
[tex]n[/tex]为偶数时呢？化成奇数做？不好，因为这样会出现对于[tex]n^{a} (a>1)[/tex]一类数会无能为力。偶数也可构造：[tex](n,(n/2)^{2}-1,(n/2)^{2}+1)[/tex]。
然后做就行了……
#include <iostream>
using namespace std;
int main(){
long long n,temp;
cin>>n;
if(n<=2){
cout<<-1<<endl;
return 0;
}
if(1&n){
temp=n*n-1;
temp/=2;
cout<<temp<<' '<<(temp+1)<<endl;
}else{
temp=n/2;
cout<<temp*temp+1<<' '<<temp*temp-1<<endl;
}
return 0;
}
[CF 371B]Fox Dividing Cheese
狐狸的三种操作的实质是除二，除三，除五。由此我们可以猜想在最优策略下，两块蛋糕最后的重量应该是[tex]gcd(a,b)[/tex]。然后试除即可。
（大胆猜想，不用证明）
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
if(!b)
return a;
else
return gcd(b,a%b);
}
static int P[3]={2,3,5};
inline int min_fj(int source,int direction){
register int i,ans=0;
source/=direction;
if(source==1)
return 0;
for(i=2;i>=0;i--){
while(source%P[i]==0){
source/=P[i];
ans++;
}
}
if(source==1)
return ans;
else
return -1;
}
int main(){
register int direction,t1,t2;
int a,b;
cin>>a>>b;
if(a==b){
cout<<0<<endl;
return 0;
}
direction=gcd(a,b);
t1=min_fj(a,direction);
if(t1==-1){
cout<<-1<<endl;
return 0;
}
t2=min_fj(b,direction);
if(t2==-1){
cout<<-1<<endl;
return 0;
}
cout<<t1+t2<<endl;
return 0;
}
