C - Distribution

题目

有(N)个人,第(i)个人会在(T_i)时刻从Takahashi手上拿到宝石.若第(i)个人在(t_i)时刻(不一定等于(T_i))拿到宝石,他会在(t_i+S_i)时刻将宝石给((i-1)%n+1)个人.

给定(N,S,T)问每个人拿到宝石的最早时间.

思路

先把(T_i)和对应的(i)捆绑起来,扔进按(T)从小到大排序的小根堆,每次从小根堆中取出(t_i)和(i),则(ans_i=t_i),将(t_i+S_i)和((i-1)\%n+1)扔进堆里即可.

代码

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

const int N = 200010;
int n;
int s[N] , t[N];
int ans[N];
struct node {
	int t , id;
	bool operator < (const node &a) const {
		return t > a.t;
	}
};
node make(int t , int id) {
	node tmp;
	tmp.t = t , tmp.id = id;
	return tmp;
}
priority_queue <node> q;
int main() {
	n = read();
	for(int i = 1 ; i <= n ; i++)
		s[i] = read();
	for(int j = 1 ; j <= n ; j++) {
		t[j] = read();
		q.push(make(t[j] , j));
	}
	while(!q.empty()) {
		node k = q.top();
		q.pop();
		if(ans[k.id] != 0)
			continue;
		ans[k.id] = k.t;
		q.push(make(k.t + s[k.id] , k.id % n + 1));
	}
	
	for(int i = 1 ; i <= n ; i++)
		printf("%d
" , ans[i]);
	return 0;
}

D - Sum of Maximum Weights

题目

给定一颗树,有(N)个结点,定义(f(u,v))为(u),(v)路径上边权的最大值,求(sum_{i=1}^{N-1}sum_{j=i+1}^Nf(i,j)).

思路

把边按照边权从小到大排序,并按顺序遍历所有边,对于每条边,它对答案的贡献为

[w_icdot size_{u_i}cdot size_{v_i} ]

(size)为点所属并查集的大小,计算答案后,合并(i,j)所在并查集.

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

typedef long long lint;
const int N = 200010;
int n;

struct EDGE {
	int u , v;
	lint w;
}ed[N];
bool cmp(EDGE x , EDGE y) {
	return x.w < y.w;
}

lint size[N];
int fa[N];
int findroot(int x) {
	return fa[x] == x ? x : (fa[x] = findroot(fa[x]));
}
void uni(int x , int y) {
	x = findroot(x) , y = findroot(y);
	if(x == y)
		return ;
	size[x] += size[y];
	fa[y] = x;
}

int main() {
	n = read();
	for(int i = 1 ; i < n ; i++)
		ed[i].u = read() , ed[i].v = read() , ed[i].w = read();
	
	for(int i = 1 ; i <= n ; i++)
		fa[i] = i , size[i] = 1;
	std::sort(ed + 1 , ed + n , cmp);
	lint ans = 0;
	for(int i = 1 ; i < n ; i++) {
		int x = findroot(ed[i].u) , y = findroot(ed[i].v);
		ans += ed[i].w * size[x] * size[y];
		uni(x , y);
	}
	std::cout << ans;
	return 0;
}

E - Packing Under Range Regulations

题目

有(10^9)个盒子编号(1)到(10^9),每个盒子可以放一个球,第(i)个球可以放在编号(l_i)到(r_i)的盒子中.给定(l,r),问:是否每个球都能放在盒子中.

思路

把每个球按照(l)从小到大排序,假设当前需要用编号为(p)的盒子,且编号为(1)到(p-1)的盒子已经不可用,有(j)个还没有放入任何一个盒子的小球,且它们都可以放在(p)盒子中.

我们肯定要先把(r)小的先放到盒子里,因为前面的盒子已经不可用,(r)大的还有可能放进后面的盒子.

因此,我们的贪心就出来了,详见代码.

~~居然被一些奇奇怪怪的小错误卡了半天.~~

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

typedef long long lint;
const int N = 2000010;
int n;

struct BALL {
	int l , r;
	bool operator < (const BALL &b) const{
		return r > b.r;
	}
}ball[N];
bool cmp(BALL a , BALL b) {
	return a.l < b.l;
}

priority_queue <BALL> q;
int main() {
	int T = read();
	while(T--) {
		while(q.size())q.pop();
		n = 0;
		
		n = read();
		for(int i = 1 ; i <= n ; i++)
			ball[i].l = read() , ball[i].r = read();
		
		sort(ball + 1 , ball + n + 1 , cmp);//左端点排序
		bool ans = true;
		int box = ball[1].l , p = 1;
		while(p <= n || !q.empty()) {
			while(ball[p].l <= box && p <= n)//可以放进编号为box的小球放入堆内,堆维护最小r
				q.push(ball[p]), ++p;
			
			if(q.empty()) {//跳过无用盒子
				box = ball[p].l;
				continue;
			}
			BALL b = q.top();//尝试将小球b放入编号为box的盒子
			q.pop();
			if(b.r < box) {//放不了
				ans = false;
				break;
			}
			++box;
		}
		puts(ans ? "Yes" : "No");
	}
	return 0;
}

F - Substrings

题目

有一个字符串(S),你可以确定一个序列(a_1,a_2,cdots a_k),满足(forall iin[1,k)quad ,a_i<a_{i+1}-1),且(k>0).定义字符串(T=S_{a_1}S_{a_2}S_{a_3}cdots S_{a_k}).

问有多少个不同的(T)

思路

考虑(a_i<a_{i+1})的情况怎么做.

设(f_i)表示在从前(i)个中选择若干字符,其中必选(i),按原本顺序能构不同的字符串的个数.则有:

[f_i=sum_{j=k}^{i-1}f_j ]

其中,(forall xin(k,i),S_x eq S_i),且(S_k=S_i,k<i),若不存在(S_k=S_i) (k=0).

特殊地,(f_0=1),表示空串.

由于(T)不能为空,答案就是(sum_{i=1}^nf_i).

回到这题.

(a_i<a_{i+1}-1).

其实变化多少,只要让(i-j>2)时才累加(f_j)即可,但是这样你会发现(i=1)时并不会累加(f_0),这不是我们想要的结果,所以,为了方便,我们让(f_{-1}=0).

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int N = 200010;
const int mod = (int)1e9+7;

int __f[N] , *f = __f + 3;
char s[N];
int n;
signed main() {
	scanf("%s" , s + 1);
	n = strlen(s + 1);
	
	f[-1] = 1;
	for(int i = 1 ; i <= n ; i++) {
		for(int j = i - 1 ; true ; --j) {
			if(i - j >= 2)
				f[i] += f[j];
			if(s[i] == s[j])
				f[i] += f[j - 1];
			if(j == -1 || s[j] == s[i])
				break;
		}
		f[i] %= mod;
	}
	int ans = 0;
	for(int i = 1 ; i <= n ; i++)
		ans += f[i];
	cout << ans % mod;
	return 0;
}