A HDU 5695 拓扑排序
m 个有序关系， 显然是拓扑排序。
要想分数最大， 先安排大数即可。 用优先队列比较好实现。
注意分数会爆int
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
//#define int long long
using namespace std;
typedef long long LL;
int T;
const int maxn = 100000 + 10;
vector<int>g[maxn];
int in[maxn];
int main(){
scanf("%d",&T);
while(T--){
// cnt = 0;
int n,m;
scanf("%d%d",&n, &m);
for (int i = 1; i <= n; ++i){
g[i].clear();
in[i] = 0;
}
for (int i = 0; i < m; ++i){
int x,y;
scanf("%d %d",&x, &y);
g[x].push_back(y);
in[y]++;
}
priority_queue<int>q;
for (int i = 1; i <= n; ++i){
if (in[i] == 0){
q.push(i);
}
}
LL ans = 0;
LL mi = LL(1e18);
while(!q.empty()){
int u = q.top();
q.pop();
mi = min(mi, (LL)u);
ans += mi;
for (int i = 0; i < g[u].size(); ++i){
int v = g[u][i];
in[v]--;
if (in[v] == 0){
q.push(v);
}
}
}
printf("%I64d\n", ans);
}
return 0;
}
/**
5
1 10 w
20 30 w
11 19 w
31 40 w
1 5 b
**/
B
告诉你n 个人的起始位置（都在数轴上）， 和最大移动速度， 求最少多少时间， 他们可以汇聚一点。
显然二分， 直接二分时间， 然后看看 n个人所构成的线段是否都有公共区域即可。
eps 开1e-6就好了 否则超时。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 120000 + 10;
double x[maxn];
double v[maxn];
const double eps = 1e-6;
int n;
int dcmp(double a,double b){
if (fabs(a-b)<eps) return 0;
if (a>b) return 1;
return -1;
}
struct Node{
double l,r;
Node(double l = 0,double r = 0):l(l), r(r){}
bool operator < (const Node& rhs) const {
return dcmp(l,rhs.l) == -1;
}
}p[maxn];
bool judge(double a){
int cnt = 0;
double mi = 1e18;
double mx = 0;
for (int i = 0; i < n; ++i){
p[i] = Node(x[i] - v[i] * a,x[i] + v[i] * a);
mi = min(mi, x[i] + v[i] * a);
mx = max(mx, x[i] - v[i] * a);
}
for (int i = 1; i < n; ++i){
if (dcmp(p[i].l, mi) > 0) return 0;
if (dcmp(p[i].r, mx) < 0) return 0;
// if (dcmp(p[i].l,p[0].r) == 1) return 0;
}
return 1;
}
int main(){
// int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i){
scanf("%lf",x+i);
}
for (int i = 0; i < n; ++i){
scanf("%lf",v+i);
}
double l = 0, r = 1e9+7;
while(r-l > eps){
double m = (l+r)/2;
// printf("%.10f\n", m);
if (judge(m))r = m;
else l = m;
}
double ans = (l + r )/2;
printf("%.14f\n", ans);
return 0;
}
/**
4
1 2 1 2
aab
aac
caa
aad
**/
C
CodeForces - 785D （组合数+逆元）
题意：
告诉你一个括号序列， 你可以删除一些括号， 问你有多少种删除方法 使得 剩下的括号 是偶数长度， 且前一半和后一半对称（当然得合法）
思路：
我们统计出每一个位置 的 f[i] 和b[i] f表示i 位置左边有多少左括号， b 表示这个位置右边有多少个右括号。
为了不重复计算， 我们显然每一次枚举 都必须用上这个位置。
我们很容易得到这个式子。
（这是 F 最小值， B是最小值 同理）
前两个式子很容易得到，关键是最后一步。
我们可以换个考虑方式。
假设甲班有F-1个同学， 乙班有B个同学， 要从两个班选F个同学。 很显然是C(F+B-1, F)个同学。
假设在乙班选i 个同学， 甲班选F-i 个同学。 那么答案就是第二个式子。
这样复杂度就是o（n）了
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
//#define int long long
using namespace std;
typedef long long LL;
const int maxn = 200000 + 10;
char s[maxn];
const int mod = 1e9+7;
int f[maxn];
int b[maxn];
LL jie[maxn];
LL rev[maxn];
LL my_pow(LL a,LL n){
LL ans = 1LL;
while(n){
if (n & 1)
ans = (ans * a) % mod;
a = (a*a)%mod;
n >>= 1;
}
return ans;
}
void init(){
jie[0] = 1;
rev[0] = 1;
for (int i = 1; i < maxn; ++i){
jie[i] = (jie[i-1] * i) % mod;
rev[i] = my_pow(jie[i], mod-2);
}
}
void add(LL& ans, LL x){
ans += x;
if (ans >= mod) ans -= mod;
}
LL C(int n, int m){
return ((jie[n] * rev[m])%mod * rev[n-m])%mod;
}
LL solve(int F,int B){
LL ans = 0LL;
add(ans, C(F+B-1,F));
return ans;
}
int main(){
init();
// cout<<C(4,2)<<endl;
scanf("%s",s+1);
int len = strlen(s+1);
for (int i = 1; i <= len; ++i){
f[i] = f[i-1];
if (s[i] == '(')f[i]++;
}
for (int i = len; i >= 1; --i){
b[i] = b[i+1];
if (s[i] == ')')++b[i];
}
LL ans = 0LL;
for (int i = 1; i <= len; ++i){
if (s[i] == '('){
add(ans, solve(f[i], b[i]));
}
}
printf("%lld\n", ans);
return 0;
}
/**
5
1 10 w
20 30 w
11 19 w
31 40 w
1 5 b
**/
D CodeForces - 706C (dp)
巨二逼的一个题， 自己因为 long long 最大值 开的是 int 最大值， 最后3分钟才改过来 = =~
直接令dp[i][0] 表示到第i 个字符串 不反转的 耗费， 和dp[i][1] 为到第i个字符串 反转的耗费。 取个最小值就好了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;
LL dp[maxn][3];
const LL inf = (LL)1e18;
string s[maxn];///0 is ok
string rev[maxn];///1 is rev
int a[maxn];
int main(){
int n;
scanf("%d",&n);
for (int i = 1; i <= n; ++i){
scanf("%d",&a[i]);
}
for (int i = 1; i <= n; ++i){
cin >> s[i];
rev[i] = s[i];
reverse(rev[i].begin(), rev[i].end());
}
// for (int i = 1; i <= n; ++i){
// cout <<s[i] << " " << rev[i]<<endl;
// }
dp[1][0] = 0;
dp[1][1] = a[1];
for (int i = 2; i <= n; ++i){
dp[i][0] = dp[i][1] = inf;
if (s[i] >= s[i-1] && dp[i-1][0] != -1){
dp[i][0] = min(dp[i-1][0], dp[i][0]);
}
if (rev[i] >= s[i-1] && dp[i-1][0] != -1){
dp[i][1] = min(dp[i-1][0] + a[i], dp[i][1]);
}
if (s[i] >= rev[i-1] && dp[i-1][1] != -1){
dp[i][0] = min(dp[i-1][1],dp[i][0]);
}
if (rev[i] >= rev[i-1] && dp[i-1][1] != -1){
dp[i][1] = min(dp[i-1][1] + a[i],dp[i][1]);
}
if (dp[i][0] == inf) {
dp[i][0] = -1;
}
if (dp[i][1] == inf) {
dp[i][1] = -1;
}
}
if (dp[n][0] != -1 && dp[n][1] != -1){
printf("%I64d\n", min(dp[n][0], dp[n][1]));
}
else if (dp[n][0] != -1){
printf("%I64d\n", dp[n][0]);
}
else if (dp[n][1] != -1) {
printf("%I64d\n", dp[n][1]);
}
else puts("-1");
return 0;
}
/**
4
1 2 1 2
aab
aac
caa
aad
**/E POJ - 3461 KMP
kmp裸题
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
//#define int long long
using namespace std;
typedef long long LL;
const int maxn = 10000 + 10;
const int maxm = 1000000 + 10;
int T;
int lent, lens;
int Next[maxm];
void get_Next(char* t){
Next[0] = Next[1] = 0;
int j;
for (int i = 1; i < lent; ++i){
j = Next[i];
while(j > 0 && t[i] != t[j]) j = Next[j];
if (t[i] == t[j])Next[i+1] = j+1;
else Next[i+1] = 0;
}
}
int kmp(char* s,char* t){
int ans = 0;
int j = 0;
for (int i = 0; i < lent; ++i){
while(j > 0 && s[j] != t[i])j = Next[j];
if (s[j] == t[i])++j;
if (j == lens)++ans;
}
return ans;
}
char s[maxn], t[maxm];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s%s",s,t);
lent = strlen(t);
lens = strlen(s);
get_Next(t);
int ans = kmp(s,t);
printf("%d\n", ans);
}
return 0;
}
/**
5
1 10 w
20 30 w
11 19 w
31 40 w
1 5 b
**/
F ZOJ - 2301线段树
看了一眼 直接想到区间合并上去了。 写的很乱。。
其实很水，直接一个区间赋值就好了。 然后暴力查询每一个点的颜色， 复杂度nlogn
离散化有点坑。
这题还不能像贴海报那样离散化。
因为那样只能保证 不会出现那种 本来不该连续 却连续的情况。
但是会在端点处出错误。
比如
5
1 10 w
11 20 w
21 30 w
31 40 w
1 5 b
应该输出 6 40
解决方法 直接在每个线段的右端点在插入一个离散化后的数就好了；
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
//#define int long long
using namespace std;
typedef long long LL;
const int maxn = 6000 + 10;
int a[maxn];
int n;
struct CCCmd{
int x,y,col;
}p[maxn];
char cmd[5];
struct node{
int L,R;
int setv;
}nod[maxn<<2];
/// 0 is black 1 is white;
void build(int l,int r,int o){
nod[o].L = l;
nod[o].R = r;
nod[o].setv = -1;
int m = l + r >> 1;
if (l == r) {
return;
}
build(l,m,o<<1);
build(m+1,r,o<<1|1);
}
void pushdown(int o){
int l = nod[o].L;
int r = nod[o].R;
if (l == r) return;
int lson = o<<1;
int rson = o<<1|1;
if (nod[o].setv != -1){
nod[lson].setv = nod[rson].setv = nod[o].setv;
nod[o].setv = -1;
}
}
void update(int L,int R,int c,int l,int r,int o){
if (L <= l && r <= R){
nod[o].setv = c;
return;
}
pushdown(o);
int m = l + r >> 1;
if (m >= L){
update(L,R,c,l,m,o<<1);
}
if (m < R){
update(L,R,c,m+1,r,o<<1|1);
}
}
int query(int pos, int l,int r,int o){
if (l == r) {
if (nod[o].setv == -1) return 0;
return nod[o].setv;
}
int m = l + r>> 1;
int lson = o << 1;
int rson = o << 1|1;
pushdown(o);
if (m >= pos){
return query(pos, l,m,lson);
}
else {
return query(pos, m+1,r,rson);
}
}
int cnt;
int get(int x){
int l = 0,r = cnt-1;
while(l <= r){
int m = l + r>> 1;
if (a[m] == x){
return m;
}
else if (a[m] > x){
r = m-1;
}
else l = m + 1;
}
}
int main(){
// cout << (1<<31) - 1 << endl;
while(~scanf("%d",&n)){
cnt = 0;
for (int i = 0; i < n; ++i){
scanf("%d%d%s",&p[i].x, &p[i].y, cmd);
if (cmd[0] == 'b') p[i].col = 0;
else p[i].col = 1;
a[cnt++] = p[i].x;
a[cnt++] = p[i].y;
a[cnt++] = p[i].y + 1;
}
sort(a,a+cnt);
int cnt2 = cnt;
for (int i = 1; i < cnt; ++i){
if (a[i] - a[i-1] > 1) a[cnt2++] = a[i]-1;
}
cnt = cnt2;
sort(a,a+cnt);
cnt = unique(a,a+cnt) - a;
build(0,cnt-1,1);
for (int i = 0; i < n; ++i){
update(get(p[i].x), get(p[i].y), p[i].col, 0, cnt-1, 1);
}
LL ans = 0LL;
int ans1, ans2;
// for (int i = 0; i < cnt; ++i){
// printf("%d %d\n", a[i], query(i, 0, cnt-1, 1));
//
// }
for (int i = 0; i < cnt; ++i){
int t = query(i, 0, cnt-1, 1);
if (t == 1){
LL sum;
int j;
for (j = i+1; j < cnt; ++j){
if (query(j, 0, cnt-1, 1) == 0)break;
}
sum = (LL)a[j-1] - (LL)a[i] + 1LL;
if (sum > ans){
ans1 = a[i];
ans2 = a[j-1];
ans = sum;
}
i = j;
}
}
if (ans == 0) puts("Oh, my god");
else printf("%d %d\n", ans1,ans2);
}
return 0;
}
/**
5
1 10 w
20 30 w
11 19 w
31 40 w
1 5 b
**/