我說這題好詭異……O(N*L)會過是毛啦orz
Nice Problem.只是我想了太久XDrz
要先有一個概念：如果最後有合奏的學姐序列依照合奏時間用S1~Sk表示。
那麼對任意i，一定有Si的編號 < S(i+1)的編號。
也就是不會有a區間比b區間前面 但是a學姐比b學姐晚合奏完的情況。
怎麼證明呢？假設最佳序列是S'1~S'k而且其中存在一個i，S'i的編號 > S'(i+1)的編號
但經過一點點的小證明可以發現，把這兩個學姐交換順序也一定存在一個合法的合奏方案。
//因為區間有非嚴格遞增性才會合理。
所以我們可以用DP[i][j]表示做完前i個學姐，取了j個學姐時最右界的位置。
每個轉移O(1)，總複雜度O(N^2)
#include<stdio.h>
bool con[40][40], pos, v[40];
char buf[100], c, d;
int n, m, K, a, b, $;
/*
m 0~n-1 h n~2n-1
*/
bool dfs(int now){
v[now]= 1;
if(now-$==n|| $-now==n)return 0;
for(int i=0; i<2*n; i++)
if(con[now][i]&& !v[i]&& !dfs(i))
return 0;
return 1;
}
int main(){
gets(buf);
sscanf(buf, "%d", &K);
while(K--){
pos= 1;
gets(buf);
sscanf(buf, "%d%d", &n, &m);
for(int i=0; i<n*2; i++)
for(int j=0; j<n*2; j++)
con[i][j]= 0;
for(int i=0; i<m; i++){
gets(buf);
sscanf(buf, "%c%d %c%d", &c, &a, &d, &b);
con[a+(c=='h'?n:0)-1][b+(d=='m'?n:0)-1]= 1;
con[b+(d=='h'?n:0)-1][a+(c=='m'?n:0)-1]= 1;
}
for($=0; pos&&$<n; $++){
for(int j=0; j<2*n; j++)v[j]= 0;
pos= dfs($);
if(!pos){
for(int j=0; j<2*n; j++)v[j]= 0;
$+=n; pos= dfs($); $-=n;
}
}
puts(pos? "GOOD": "BAD");
}
}
#include<stdio.h>
int top, n, cnt;
struct node{
node *lch, *rch;
int val;
}N[10020], *st[10020];
void dfs(node *now){
if(now==NULL)return;
printf("%d%c", now->val, ++cnt==n? '\n': ' ');
dfs(now->lch);
dfs(now->rch);
}
int main(){
N[0].val= -1;
while(~scanf("%d", &n)){
if(!n) break;
cnt= 0;
top= 0; N[0].lch= N[0].rch= NULL;
for(int i=1; i<=n; i++){
scanf("%d", &N[i].val);
N[i].lch= N[i].rch= NULL;
}
st[top]= N;
for(int i=1; i<=n; i++){
while(top> -1&& st[top]->val>N[i].val){
N[i].lch= st[top];
--top;
}
st[top]->rch= &N[i];
st[++top]= &N[i];
}
dfs(N[0].rch);
}
}
#include<algorithm>
#define MOD 1000000007
#define lb(x) ((x)&(-x))
int bit[1010][1010], r, c, T, cnt;
int qry(int i, int j){
int ret= 0;
for(; i>0; i-=lb(i))
for(int jj=j; jj>0; jj-=lb(jj)){
ret+= bit[i][jj];
ret%=MOD;
}
return ret;
}
void adj(int i, int j, int v){
for(; i<=r; i+=lb(i))
for(int jj=j; jj<=c; jj+=lb(jj)){
bit[i][jj]+= v;
bit[i][jj]%=MOD;
}
}
struct com{
int i,j,h;
bool operator<(const com &b)const{
return h<b.h|| ( h==b.h&& (i>b.i|| i==b.i&&j>b.j ) );
}
void get(int a, int b){
scanf("%d", &h);
i= a; j= b;
}
}cc[1001000];
int main(){
scanf("%d", &T);
while(T--){
scanf("%d%d", &r, &c);
//Init
cnt= 0;
for(int i=1; i<=r; i++)
for(int j=1; j<=c; j++)
bit[i][j]= 0;
for(int i=1; i<=r; i++)
for(int j=1; j<=c; j++)
cc[cnt++].get(i, j);
std::sort(cc, cc+cnt);
for(int i=0; i<cnt; i++){
int ii=cc[i].i, jj=cc[i].j;
adj(ii, jj, qry(ii, jj)+1);
}
printf("%d\n", qry(r, c));
}
}
#include<stdio.h>
int n, k, match[1010], cCnt, mCnt, a, b;
bool con[1010][1010], vst[1010];
bool aug(int now){
for(int i=1; i<=n; i++)
if(!vst[i]&& con[now][i]){
vst[i]= 1;
if(match[i]==-1|| aug(match[i])){
match[i]= now;
return 1;
}
}
return 0;
}
int main(){
while(~scanf("%d%d", &n, &k)){
if(!n&& !k) break;
mCnt= 0;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; j++)
con[i][j]= 0;
match[i]= -1;
}
for(int i=0; i<k; ++i){
scanf("%d%d", &a, &b);
con[a][b]= 1;
}
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j) vst[j]= 0;
if(aug(i)) ++mCnt;
}
printf("Case #%d:%d\n", ++cCnt, mCnt);
}
}
#include<stdio.h>
#define MAXV 100100
int T, n, m, stamp, tt, a, b, cnt, eCnt, _tar;
int vst[MAXV], can;
struct edge{
int i, j;
edge *next;
void set(int a, int b, edge **vv){
edge *p= vv[a];
vv[a]= this; i=a; j=b; next= p;
}
}e[MAXV*20], *v[MAXV], *vr[MAXV];
void dfs(int now){
vst[now]= 1;
for(edge *p=v[now]; p; p=p->next)
if(!vst[p->j])
dfs(p->j);
stamp= now; ++tt;
}
void dfsr(int now){
vst[now]= 1; ++cnt;
for(edge *p=v[now]; p; p=p->next)
if(!vst[p->j])
dfsr(p->j);
}
int dfs3(int now){
int t;
vst[now]= _tar;
for(edge *p=v[now],*q=NULL; p; p=p->next){
if(vst[p->j]== _tar){
eCnt++;
if(q)q->next= p->next;
else v[now]= p->next;
return p->j;
}
else{
t= dfs3(p->j);
if(t!=0){
eCnt++;
if(q){q->next= p->next;}
else v[now]= p->next;
if(t!=now){
return t;
}
}else q=p;
}
}
return 0;
}
int main(){
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
//init
for(int i=0; i<=n; i++){
vst[i]= 0;
v[i]= vr[i]= NULL;
}
can= 1; tt= cnt= eCnt= 0;
//input
for(int i=0; i<m; i++){
scanf("%d%d", &a, &b); ++a; ++b;
e[i].set(a, b, v);
e[i+m].set(b, a, vr);
}
//dfs
dfs(1);
if(tt!= n){puts("NO"); continue;}
for(int i=1; i<=n; i++) vst[i]= 0;
dfsr(stamp);
if(cnt!= n){puts("NO"); continue;}
for(int i=1; i<=n; i++) vst[i]= 0;
for(int i=1; i<=n; i++){
_tar= i;
dfs3(i);
}
puts(eCnt== m? "YES": "NO");
}
}
#include<stdio.h>
unsigned val[100010], n, q, a, b;
struct seg{
unsigned l, r, v1, v2;
seg *lch, *rch;
unsigned max(unsigned,unsigned);
unsigned min(unsigned,unsigned);
}s[300000];
seg *get(unsigned l, unsigned r){
static int cnt=0;
s[cnt].l=l; s[cnt].r=r; s[cnt].v1=0; s[cnt].v2=222222222u;
return s+cnt++;
}
unsigned seg::max(unsigned _l, unsigned _r){
//printf(">>%u %u\n",l,r);
if(l== r)return v1= val[l];
unsigned m1, m2, mid=(l+r)/2;
if(!lch){
lch= get(l, mid);
rch= get(mid+1, r);
}
if(_l==l&& _r==r){
if(!v1){
m1= lch->max(l, mid);
m2= rch->max(mid+1, r);
v1= m1>m2?m1:m2;
}return v1;
}
if(_l> mid)
return rch->max(_l, _r);
else if(_r<= mid)
return lch->max(_l, _r);
else{
m1= lch->max(_l, mid);
m2= rch->max(mid+1, _r);
return m1>m2?m1:m2;
}
}
unsigned seg::min(unsigned _l, unsigned _r){
if(l== r)return v2= val[l];
unsigned m1, m2, mid=(l+r)/2;
if(_l==l&& _r==r){
if(v2==222222222u){
m1= lch->min(l, mid);
m2= rch->min(mid+1, r);
v2= m1<m2?m1:m2;
}return v2;
}
if(_l> mid)
return rch->min(_l, _r);
else if(_r<= mid)
return lch->min(_l, _r);
else{
m1= lch->min(_l, mid);
m2= rch->min(mid+1, _r);
return m1<m2?m1:m2;
}
}
int main(){
scanf("%u %u", &n, &q);
for(int i=1; i<=n; i++)
scanf("%u", val+i);
get(1, n);
while(q--){
scanf("%u%u", &a, &b);;
printf("%u\n", s[0].max(a,b)-s[0].min(a,b));
}
}
#include<algorithm>
struct skill{
int s, a;
bool operator< (const skill &b)const{return a< b.a;}
void get(){scanf("%d%d", &s, &a);}
}s[1000010], h[1000010];
bool cmp(skill a, skill b){return a.s< b.s;}
int t, k, n, min, top;
int main(){
scanf("%d", &t);
while(t--){
top= 0; min= 2147483647;
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++)
s[i].get();
std::sort(s, s+n, cmp);
for(int i=0; i<n; ){
int ns= s[i].s;
while(i<n && s[i].s== ns){
h[top++]= s[i];
std::push_heap(h, h+top);
i++;
}
if(top< k)continue;
while(top> k){
std::pop_heap(h, h+top--);
}
ns+= h[0].a;
if(ns< min)min= ns;
}
printf("%d\n", min);
}
}
char buf[30];
long long val;
int main(){
while(gets(buf)){
if(buf[0]=='0')break;
val=0;
for(int i=0; buf[i]; i++){
if(buf[i]>'6')buf[i]--;
val= val*9+buf[i]-48;
}
printf("%I64d\n",val);
}
}
