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

[CF 705C]Thor

这题我考试的时候想出各种蜜汁数据结构。

但是正解是:暴力!

好了好了,暴力也是要优化的。首先给消息编号,然后用一个bitset记下来哪个删了哪个没删,这个都能想到。

不过接下来有个挺头疼的问题:操作3阅读的信息可能在操作2中会被再次阅读,如此一来效率就很低了……咋整?

注意大消息队列里的消息编号肯定是升序的,每个程序的消息队列的编号也是升序的,所以说大队列中同一程序的消息的编号和该程序自身队列中的消息编号的顺序是一致的。如此一来,在操作3中可以顺便把程序队列中的消息也删掉,效率大为提升。

代码:

#include <cstdio>
#include <queue>
#include <utility>
#include <cctype>
#include <bitset>
using namespace std;
const int maxn=300001;
typedef pair<int,int> pii;
bitset<maxn> vis;
queue<int> S[maxn];
queue<pii> Q;
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
	register int ans=0,cnt=0;
	register int temp,temp_2,q,u,v;
	int n;
	n=readint();
	q=readint();
	while(q--){
		u=readint();
		v=readint();
		if(u==1){
			cnt++;
			S[v].push(cnt);
			Q.push(make_pair(v,cnt));
			ans++;
		}else{
			if(u==2){
				while(!S[v].empty()){
					temp=S[v].front();
					S[v].pop();
					if(!vis[temp]){
						vis[temp]=true;
						ans--;
					}
				}
			}else{
				while(!Q.empty() && (temp=Q.front().second)<=v){
					temp=Q.front().second;
					temp_2=Q.front().first;
					Q.pop();
					if(!vis[temp]){
						vis[temp]=true;
						S[temp_2].pop();
						ans--;
					}
				}
			}
		}
		writeint(ans);
		putchar('\n');
	}
	return 0;
}

[CF 676B]Pyramid of Glasses

这题可以直接模拟,貌似也可过。但复杂度很高。

我们可以直接把t个单位的酒放入第一个杯,然后向下溢出,以此类推,这样复杂度就很优秀了。

代码:

#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
	int i,ans=0;
	long double temp;
	if(x>n)
		return 0;
	for(i=1;i<=n;i++){
		if(k[x][i]>=1.0){
			ans++;
			if(k[x][i]>1.0 && x<n){
				temp=(k[x][i]-1.0)/2;
				k[x][i]=1.0;
				k[x+1][i]+=temp;
				k[x+1][i+1]+=temp;
			}
		}
	}
	return ans+call(x+1);
}
int main(){
	cin>>n>>k[1][1];
	cout<<call(1)<<endl;
	return 0;
}