[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;
}