A.Toda 2
思路：可以有二分来得到最后的数值，然后每次排序去掉最大的两个，或者3个（奇数时）。
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016��10��24�� ����һ 15ʱ00��28��
**Problem** : /media/ray/708898B888987E72/Users/Administrator/Desktop/2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)/erfen_a.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = ; int a[maxn],n; struct node{
int i,v;
}b[maxn];
vector<string> outp;
bool cmp(const node &a,const node &b){
return a.v>b.v;
}
bool check(int tar){
if(tar==)return true;
for(int i=;i<=n;i++)b[i]=(node){i,a[i]-tar};
sort(b+,b++n,cmp); int leftsu=;
for(int i=;i<=n;i++)leftsu+=b[i].v;
if(leftsu<b[].v)return false;
if(n==&&(b[].v+leftsu)%!=)return false;
return true;
}
void add(int i,int j){
string t;
for(int i=;i<n;i++)t+='';
t[i-]=t[j-]='';
outp.push_back(t);
}
void add(int i,int j,int k){
string t;
for(int i=;i<n;i++)t+='';
t[i-]=t[j-]=t[k-]='';
outp.push_back(t);
}
void out(int tar){
printf("%d\n",tar);
if(tar==){
for(int i=;i<n;i++)for(int j=;j<;j++)add(i,i+);
for(int j=;j<;j++)add(n,);
}else{
for(int i=;i<=n;i++)b[i]=(node){i,a[i]-tar};
sort(b+,b++n,cmp); int su=;
for(int i=;i<=n;i++)su+=b[i].v; if(su%==){
add(b[].i,b[].i,b[].i);
b[].v--;b[].v--;b[].v--;
sort(b+,b++n,cmp);
} while(b[].v){
add(b[].i,b[].i);
b[].v--;
b[].v--;
sort(b+,b++n,cmp);
}
}
cout<<outp.size()<<endl;
for(int i=;i<outp.size();i++){
cout<<outp[i]<<endl;
}
} int main(void)
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
int l=,r=;for(int i=;i<=n;i++)if(a[i]<r)r=a[i];
while(l<=r){
int m=l+r>>;
if(check(m))l=m+;
else r=m-;
}
out(r);
return ;
}
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016年10月24日 星期一 17时20分20秒
**Problem** : cf730b.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = 1e5 + ; bool com(int i,int j){
cout<<"? "<<i<<" "<<j<<endl;
char c;
cin>>c;
return c=='<';
}
int t,n;
int main(void)
{
cin>>t;
while(t--){
cin>>n;
int ma,mi;
if(n%==)
ma=mi=;
else
if(com(,)) mi=,ma=;
else mi=,ma=; for(int i=n%==?:;i<=n;i+=){
if(com(i,i+)){
if(com(i,mi))mi=i;
if(com(ma,i+))ma=i+;
}else{
if(com(i+,mi))mi=i+;
if(com(ma,i))ma=i;
}
}
cout<<"! "<<mi<<" "<<ma<<endl;
}
return ;
}
C.Bulmart
给1个n点m边简单图（可能不是联通分量），每条边一样长度（就说花费时间一样），一些边上有商店，第i个商店放ci点，有价格pi的ki个货物，q次询问，目的地gi需要ri个货物且不能花超过ai，求能否满足此询问，能的话求出最小的运送最长时间
一开始想用网络流做的，发现其实只是取多个最小值问题就直接转问题思路。做法是对每次询问，从目的地跑bfs，把对应位置商店置一下距离，二分路程求最小路程可满足需求
为了在找到解时直接return，预处理时商店列表以单价递增的方式排序
这里有个问题，就是询问这里是o(qwlogn)+o(qw)，1000*5000*12=6*10^7，可能1500ms不能满足，而且@Deep♂Dark♂Fantasy ，为什么你们是o(qwlogn)+o(nw)的还能过？
补：ACdream回答是CF 1s=2~3*10^8次运算，所以能过，顺带HDU 1s=10^8次运算
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016年10月25日 星期二 15时44分33秒
**Problem** : cf730c.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef __int64 ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = 5e3 + ; int n,m;
int w,u,v,q,r,g,a;
vector<int> to[maxn];
queue<int> que;
int dist[maxn][maxn];
struct St{
ll c,k,p;
}st[maxn];
vector<struct St>tt;
bool cmp(struct St a,struct St b){
return a.p<b.p;
}
void bfs(int beg)
{
memset(dist[beg],-,sizeof(dist[beg]));
dist[beg][beg]=;
que.push(beg);
while(!que.empty()){
int te=que.front();que.pop();
for(int i=;i<to[te].size();i++){
int nex=to[te][i];
if(dist[beg][nex]==-){
dist[beg][nex]=dist[beg][te]+;
que.push(nex);
}
}
}
}
bool check(int beg,int dis,int rr,int aa)
{
tt.clear();
for(int i=;i<=w;i++)
if(dist[beg][st[i].c]<=dis&&dist[beg][st[i].c]!=-)
tt.push_back(st[i]);
ll num=,ans=;
for(int i=;i<tt.size();i++){
if((tt[i].k+num)<=rr)num+=tt[i].k,ans+=tt[i].k*tt[i].p;
else ans+=(rr-num)*tt[i].p,num=rr;
if(num==rr&&ans<=aa)return true;
}
return false;
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
to[u].push_back(v);
to[v].push_back(u);
}
for(int i=;i<=n;i++){bfs(i);}
scanf("%d",&w);
for(int i=;i<=w;i++)
scanf("%I64d%I64d%I64d",&st[i].c,&st[i].k,&st[i].p);
sort(st+,st++w,cmp);
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&g,&r,&a);
int ll=,rr=n,mid,ans=-;
while(ll<=rr){
mid=(ll+rr)>>;
if(check(g,mid,r,a))ans=mid,rr=mid-;
else ll=mid+;
}
printf("%d\n",ans);
}
return ;
}
D.running over the bridge
有n座桥，每座桥si长，人走在上面后ti秒就倒，人的速度是0.5，有无限瓶能量饮料，喝一瓶可以在r秒内变成1速度，但是只能在整数时点喝，且不能在效果持续时喝（T时喝，T+ti时可以再喝，中间不可以喝）
xjb贪心，把喝饮料的开始时间尽量延迟，然后二分推
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016年10月28日 星期五 09时48分11秒
**Problem** : cf730d.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef __int64 ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = 2e5 + ; ll n,r;
ll l[maxn],t[maxn];
queue<ll>q;
int main(void)
{
scanf("%I64d%I64d",&n,&r);
for(int i=;i<=n;i++)scanf("%I64d",&l[i]);
for(int i=;i<=n;i++)scanf("%I64d",&t[i]);
ll mt=,ans=,tt=;
for(int i=;i<=n;i++){
if(l[i]>t[i]){printf("-1\n");return ;}
if(*l[i]<=t[i]){
if(mt)tt+=mt>l[i]?l[i]:l[i]*-mt,mt=mt>l[i]?mt-l[i]:;
else tt+=l[i]*;
continue;
}//don't have to jiasu
ll te=*l[i]-t[i];//need to add speed. mt:the add rest
if(mt>=te){tt+=mt>l[i]?l[i]:(l[i]*-mt);mt=mt>l[i]?mt-l[i]:;continue;}
else if(mt!=){tt+=mt;l[i]-=mt;t[i]-=mt;i--;mt=;continue;}
else{
ll a=te/r,b=te%r;
ans+=b==?a:a+;
if(ans<=)
for(ll j=tt+(l[i]-te)*;j<tt+t[i];j+=r)q.push(j);
tt+=l[i]*-te;
mt=b==?:(a+)*r-te;
}
}
printf("%I64d\n",ans);if(ans>)return ;
while(!q.empty()){printf("%I64d ",q.front());q.pop();}
return ;
}
E.award ceremony
在另外一个世界，icpc比赛的排序方式是：分数高的排位高，其次id值小的排位高。并且，最后1小时也会封榜，最后才揭晓真正排名，一个个队改变排名
问：如何安排各个队的分数改变顺序，使排名变化次数较多？（点数最多100）
起初我想用树状数组的方法，就是把2组状态集合到一起排序，然后每次贪心移动。
但是一直都没法让数据与我的想法对接
看到一些人的思路才“na ru ho do”每对点的影响都要算和，对答案贡献：点对间如果没有交叉是0，包含关系或交叉但是增减方向相反的肯定是1，交叉并且增减方向相同就是2
这样就轻易出解了。。。白纠结那么久
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016年10月29日 星期六 10时49分45秒
**Problem** : cf730e.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = ; struct node{
int num,ran,add;
bool operator < (const node &a)const{
return num>a.num||(num==a.num&&ran<a.ran);
}
}a[maxn];
int ok(int i,int j){
node x=a[i],y=a[j],xx=x,yy=y;
xx.num+=x.add,yy.num+=y.add;
if(x<y&&yy<xx)return ;
if(y<x&&xx<yy)return ;
if(x<y&&y<xx&&xx<yy)return ;
if(y<x&&x<yy&&yy<xx)return ;
if(yy<xx&&xx<y&&y<x)return ;
if(xx<yy&&yy<x&&x<y)return ;
return ;
}
int main(void)
{
int n,ans=;
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d %d",&a[i].num,&a[i].add),a[i].ran=i;
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
ans+=ok(i,j);
}
}
printf("%d\n",ans);
return ;
}
题意：n天在饭馆吃饭，第i天花费cost(i)，奖券最多使用floor(cost(i)/2)，使用奖券p点，可以省p元，得到floor((a(i)-p)/10)点奖券，问如何使用可以最大化优惠
之前一直想用o(nlogn)贪心做，从左到右，发现思路太过复杂，把优惠尽量往后推，但是发现如果用除法得到优惠点数，思路比较麻烦
右边的不仅要加1点，要是剩余奖券积了10张还要再处理
剩余的还要再往左遍历一遍，把最大的零头用奖券处理
后来发现不用这么麻烦，消费请求组什么的不用看做1个数字，而是多个数据放到列表来处理
遍历顺序也不正着来，反着来的话，可以把优惠尽量往后推
也不用考虑剩余奖券的问题，因为昨天不能用今天可以用的奖券，直接无视，只保存消费请求
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std; int n, coin, money;
int a[];
int expire[];
vector<int> fre, locked[];
int ans[]; void add_fre(int amount, int id) {
for(int i=;i<amount;i++)
fre.push_back(id);
} void try_spend_fre(int &amount) {
while(amount && fre.size()) {
ans[fre.back()] ++;
amount --;
fre.pop_back();
}
}
void try_spend(int &amount) {
try_spend_fre(amount);
for(int i=;i> && amount;i--)
while(amount && locked[i].size()) {
amount --;
int id = locked[i].back();
locked[i].pop_back();
add_fre(i, id);
try_spend_fre(amount);
}
} int main() {
scanf("%d%d", &n, &coin);
money = ;
for(int i=;i<=n;i++) {
scanf("%d", &a[i]);
// 先佯装全额付账，攒冥币..
int today_coin = a[i] / ;
expire[i+] = today_coin; // 今天挣了多少个币，这些币反着for时第i+1天不用就没得用了 money += a[i];
} for(int i=n;i>;i--) {
int today_discount = a[i]/; // 大if出没注意！！如果第i+1天有剩余的钱，今天虽然没法花，但是相应的锁也不必加了。
// 这个情况包含了最后一天花不出去的情况。
int lock_fre = expire[i+]; // 付了也没法多得到冥币的零头，一开始就没锁定
int today_fre = min(a[i]%, today_discount);
add_fre(today_fre, i);
today_discount -= today_fre; // 需要花1个冥币才能解锁的部分
for(int j=today_discount / ; j>; j--)
if (lock_fre) {
lock_fre --;
add_fre(, i);
} else locked[].push_back(i);
today_discount %= ; if (today_discount) {
if (lock_fre) add_fre(today_discount, i);
else locked[today_discount].push_back(i);
} try_spend(expire[i]); // 尝试把今天过期的币用掉
}
try_spend(coin);
for(int i=;i<=n;i++)
money -= ans[i];
printf("%d\n", money);
for(int i=;i<=n;i++)
printf("%d%c", ans[i], i<n ? ' ' : '\n'); return ;
}
顺带来一发未完成的
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cstring>
#include <fstream>
using namespace std;
typedef __int64 ll;
const int N=;
int min(int a,int b){return a<b?a:b;}
int a[N],b[N];
int main()
{
int n,bon,i,sum=;
scanf("%d%d",&n,&bon);
for(i=;i<n;i++)
{
scanf("%d",a+i);
int lim=a[i]/;
int m10=(lim-a[i]%)/;//the most bonus*10
if(bon<a[i]%)b[i]=;
else b[i]=a[i]%+min(m10,(bon-a[i]%)/)*;
bon-=b[i];
if(i!=)
{
while(b[i-]>= && lim>=b[i]+)
{
b[i-]-=;
b[i]+=;
bon++;
if(bon== && lim>=b[i]-)
bon-=,b[i]+=;
}
}
bon+=(a[i]-b[i])/;
}
int proc=bon;
bon-=(a[n-]-b[n-])/;
int min1=bon,spe=min(bon,a[n-]/-a[n-]+b[n-]);
b[n-]+=spe;
bon-=spe;
spe=;
for(i=n-;i>=;i--)
{
bon+=
}
for(i=;i<n;i++)sum+=a[i]-b[i];
printf("%d\n",sum);
for(i=;i<n;i++)printf("%d%c",b[i],i!=n-?' ':'\n');
return ;
}
G. Car Repair Shop
#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <list>
using namespace std;
const int maxn = ;
#define ll long long
int main()
{
int n;
scanf("%d", &n);
int s[], d[];
for (int i = ;i < n;i++) {
scanf("%d%d", &s[i], &d[i]);
bool change = false;
for (int j = ;j < i;j++) {
if (!((s[i] + d[i] <= s[j]) || (s[i] >= s[j] + d[j]))) {
if (change == false) {
s[i] = ;
j = -;
change = true;
}
else {
s[i] = s[j] + d[j];
j = -;
}
}
}
printf("%d %d\n", s[i], s[i] + d[i] - );
}
return ;
}
H.Delete Them
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016年10月24日 星期一 16时41分41秒
**Problem** : cf730h.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = ; int n,m;
char s[maxn][maxn];
char t[maxn];
int nu[maxn],len[maxn];
bool vis[maxn];
bool match(int v)
{
int c=strlen(s[v]);
if(c!=len[])return ;
for(int i=;i<len[];i++){
if(t[i]!='?'&&t[i]!=s[v][i])return ;
}
return ;
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)scanf("%s",s[i]);
for(int i=;i<m;i++)scanf("%d",&nu[i]),nu[i]--,vis[nu[i]]=true;
for(int i=;i<m;i++){
len[i]=strlen(s[nu[i]]);
if(len[i]!=len[]){
printf("No\n");return ;
}
}
for(int i=;i<len[];i++){
t[i]=s[nu[]][i];
for(int j=;j<m;j++){
if(t[i]!=s[nu[j]][i])t[i]='?';
}
}
for(int i=;i<n;i++)
if(!vis[i])
if(match(i)){
printf("No\n");return ;
}
t[len[]]='\0';
printf("Yes\n%s\n",t);
return ;
}
I.Olympiad in Programming and Sports
思路：本题的关键在于建图，由源点连接到p点以及s点容量为p以及s，p点以及s点连接n个点，花费为a[]或者b[],再由这n个点连接汇点，然后直接跑网络模板
当然也可以用基础值+差分化+贪心过
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016年10月27日 星期四 20时17分23秒
**Problem** : cf730i_flow.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = 5e4 + ;
const int maxm=;
struct Edge{
int to,next,cap,flow,cost;
}edge[maxm];
int head[maxn],tol;
int pre[maxn],dis[maxn];
bool vis[maxn];
int N;
void init(int n)
{
N=n;
tol=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].flow=;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].to=u;
edge[tol].cap=;
edge[tol].cost=-cost;
edge[tol].flow=;
edge[tol].next=head[v];
head[v]=tol++;
}
bool spfa(int s,int t)
{
queue<int>q;
for(int i=;i<N;i++){
dis[i]=INF;
vis[i]=false;
pre[i]=-;
}
dis[s]=;
vis[s]=true;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
if(pre[t]==-)return false;
else return true;
}
ll minCostMaxflow(int s,int t){
ll flow=;
ll cost=;
while(spfa(s,t)){
int Min=INF;
for(int i=pre[t];i!=-;i=pre[edge[i^].to]){
if(Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
}
for(int i=pre[t];i!=-;i=pre[edge[i^].to]){
edge[i].flow+=Min;
edge[i^].flow-=Min;
cost+=edge[i].cost*Min;
}
flow+=Min;
}
return cost;
}
int a[maxn],b[maxn];
vector<int>aa,bb;
int main(void)
{
int n,p,s;
scanf("%d%d%d",&n,&p,&s);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)scanf("%d",&b[i]);
init(n+);
for(int i=;i<=n;i++){
addedge(,i,,);
addedge(i,n+,,-a[i]);
}
for(int i=;i<=n;i++){
addedge(i,n+,,-b[i]);
}
addedge(n+,n+,p,);
addedge(n+,n+,s,);
printf("%lld\n",-minCostMaxflow(,N-));
for (int u = ; u <= n; u++){
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(!edge[i].flow)continue;
if(v==(n+))aa.push_back(u);
if(v==(n+))bb.push_back(u);
}
}
int sz=aa.size();
for(int i=;i<sz;i++)printf("%d%c",aa[i],i==(sz-)?'\n':' ');
sz=bb.size();
for(int i=;i<sz;i++)printf("%d%c",bb[i],i==(sz-)?'\n':' ');
return ;
}
J.Bottles
给n个瓶子，容量bi剩余ai液体，在把所有液体合到最少瓶子的前提下液体转移最少，问最后有液体瓶子数量和转移液体量
发现转移液体量就是几个瓶子剩下的液体量，可以先贪心一波把液体一起倒在容量最大的几个瓶，发现还有某些情况会让贪心失效（容量大，剩余小）
不够这个步骤可以确定最少用几个瓶
一开始想到搜索，有序性搜索元素。然而100个瓶子，剪枝了都不够
计算过程发现可以把几个状态按照第几个瓶子（按容量递减剩余递减排序）总容量和实际选中瓶子数合并状态数
然后就愉快地dp了
/************************************************
*Author* : Ray(siludose)
*Created Time* : 2016年10月26日 星期三 19时27分49秒
**Problem** : cf730f.cpp
**Analyse** :
**Get** :
**Code** :
*********************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define pri(a) printf("%d\n",(a))
#define xx first
#define yy second
const int mod = int(1e9) + , INF = 0x3f3f3f3f;
const int maxn = + ; int dp[maxn][];
int an[maxn][];
int n,a[maxn],b[maxn];
int main(void)
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)scanf("%d",&b[i]);
memset(dp,0x3f,sizeof(dp));
memset(an,0x3f,sizeof(an));
int kk=;dp[][kk]=;an[][kk]=;
for(int i=;i<=n;i++){
for(int j=;j<=;j++){
if(dp[i][j-a[i]]>dp[i-][j]){
dp[i][j-a[i]]=dp[i-][j];
an[i][j-a[i]]=an[i-][j]+a[i];
}else if(dp[i][j-a[i]]==dp[i-][j]){
an[i][j-a[i]]=min(an[i][j-a[i]],an[i-][j]+a[i]);
}
if(dp[i][j+b[i]-a[i]]>dp[i-][j]+){
dp[i][j+b[i]-a[i]]=dp[i-][j]+;
an[i][j+b[i]-a[i]]=an[i-][j];
}else if(dp[i][j+b[i]-a[i]]==dp[i-][j]+){
an[i][j+b[i]-a[i]]=min(an[i][j+b[i]-a[i]],an[i-][j]);
}
}
}
int ans=0x3f3f3f3f;
int num=0x3f3f3f3f;
for(int i=;i<=;i++){
if(dp[n][i]<ans){
ans=dp[n][i];num=an[n][i];
}else if(dp[n][i]==ans){
num=min(num,an[n][i]);
}
}
printf("%d %d\n",ans,num);
return ;
}
一个联通无向图（最多400000个点，1000000条边）把所有边改成有向边，使s点为唯一源点，t为唯一汇点，且没有有向环
唯一源点和汇点判断比较容易，从s点dfs一次求各点深度，求出dep（深度）表和fa（祖先）表，t点bfs一次，边有没走2次的就是不唯一
难点在于如何让路径变成没有有向环
画几个图就会发现，环上1、2条链且源点汇点属于不同树时可以构造无环路，多了会变成不唯一源点汇点
其他类似的例如8字形的图因为不存在分叉的情况（有的话遍历2次后直接筛出来了），且有时从源点到汇点的路径不会走到与环相切的位置
此外环上有树（或者说从源点到汇点的路径会走到与环相切的位置）会让路径一定出现有向环（2个点属于相同树）/源点汇点不唯一（2个点属于不同树）
想到这一步就没有思路了。。。感谢codeforces的开源机制，让我理解了那些大神的做法
碰到非树边（遍历图时边没走，目标点也没走的情况就是树边，这里是指边没走，目标点走过了）在另一个图建立映射图映射本体图
建立映射边是建son(v)->u不是v->u
因为可能v是源点，而画必经之路是从深度大的遍历完再走深度小的，如果v->u会因为fa[u]=-1有一些本该标记的边不会被标记
这样如果碰到从源点到汇点的路径会走到与环相切位置的情况时，映射图的边是映射在非必经之路上的（从汇点沿fa表走不到环边），不影响结果
没有分叉且不会走到与环相切的点，映射图的边会映射到另一条必经之路，再沿fa表走，填满另一条路
之后遍历对应无向边，全部都是必经之路就是有解
最后SB了，把边的数组大小开成点的数据大小，结果WA17...改了之后马上AC
#pragma comment(linker, "/STACK:102400000,102400000")
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cassert>
#include <ctime>
#include <cstring>
#include <fstream>
using namespace std;
typedef __int64 ll;
const int V=;
const int E=;
int to0[E],to1[E],id0[E],id1[E],nxt0[E],nxt1[E];
int head0[V],head1[V],cnt0,cnt1,n;
int fa[V],son[V],dep[V],edg[V];
bool vis[V];
void addedge(int u,int v,int edgeid)
{
to0[cnt0]=v;id0[cnt0]=edgeid;nxt0[cnt0]=head0[u];head0[u]=cnt0++;
to0[cnt0]=u;id0[cnt0]=edgeid;nxt0[cnt0]=head0[v];head0[v]=cnt0++;
} void adde(int u,int v,int edgeid)
{
to1[cnt1]=v;id1[cnt1]=edgeid;nxt1[cnt1]=head1[u];head1[u]=cnt1++;
} void dfs(int s,int depth)
{
//printf("\r%d",s);
assert(depth<=n+);
assert(s<=n);
vis[s]=true;
for(int i=head0[s];i!=-;i=nxt0[i])
{
int v=to0[i];
assert(v<=n);
if(v==fa[s])continue;
if(!vis[v])
{
edg[v]=id0[i];
dep[v]=dep[s]+;
son[s]=v;
fa[v]=s;
dfs(v,depth+);
}
else if(dep[v]<dep[s])
adde(son[v],s,id0[i]);
}
} pair<int,int> que[V<<];
int dire[E]; void bfs(int t)
{
int tal=,hed=;
queue<pair<int,int> > que;
que.push(make_pair(t,));
while(!que.empty())
{
pair<int,int> pii=que.front();
int u=pii.first,di=pii.second;
que.pop();
while(fa[u]!=- && dire[edg[u]]==-)
{
assert(u<=n);
dire[edg[u]]=di;
for(int i=head1[u];i!=-;i=nxt1[i])
{
int v=to1[i];
assert(v<=n);
dire[id1[i]]=di;
que.push(make_pair(v,di^));
}
u=fa[u];
}
}
} int tu[E],tv[E]; int main()
{
//freopen("pro.in","r",stdin);
int T,m,s,t,i;
scanf("%d",&T);
while(T--)
{
bool flag=false;
scanf("%d%d%d%d",&n,&m,&s,&t);
memset(dire,-,sizeof(int)*(m+));
memset(vis,,sizeof(bool)*(n+));
memset(head0,-,sizeof(int)*(n+));cnt0=;
memset(head1,-,sizeof(int)*(n+));cnt1=;
for(i=;i<m;i++)
{
scanf("%d%d",tu+i,tv+i);
addedge(tu[i],tv[i],i);
}
dep[s]=;fa[s]=-;
dfs(s,);
bfs(t);
for(i=;i<m;i++)
{
if(dire[i]==-){flag=true;break;}
}
if(flag)puts("No");
else
{
puts("Yes");
for(i=;i<m;i++)
{
if((dep[tu[i]]<dep[tv[i]])==dire[i])tu[i]^=tv[i]^=tu[i]^=tv[i];
printf("%d %d\n",tu[i],tv[i]);
}
}
}
return ;
}
给一段表达式，每次查询截取区间内表达式，问那段表达式的运算结果，如果不符合表达式的组成规律，输出-1
咋看是个很难缠的线段树题，仔细一看因为不涉及修改，其实线性查询就可以解决
左右各扫一遍，1个括号1个栈元素，不用递归，直接在构造表时推栈
碰到左括号时升栈，碰到右括号时降栈
至于其他3种符号就用类似于2016弱校10.3 J的处理方式
a1表示上一个加号左边的和，a2表示上一个加号右边上一个乘号左边的积，a3表示目前的右边数字，初始a1=0 a2=1 a3=0
碰到数字把a3*10+str[i]-'0'
碰到乘号把a2*=a3,a3=1
碰到加号把a1+=a2*a3,a2=1,a3=0
查询时先看左右是否是'+' '*'，左边是否')' 右边是否'('
再匹配括号，看不同位置匹配的括号层数是否一样
完了再组合算式出结果
#include <cstdio>
typedef __int64 ll;
const int xn = ;
const __int64 MOD = ;
int
N, Q, D,
pb[xn], pp[xn], pm[xn],
sb[xn], sp[xn], sm[xn],
Lb[xn], Lp[xn], Lm[xn];
char a[xn];
__int64
P10[xn], iP10[xn],
Ab[xn], Ap[xn], Az[xn], Am[xn],
ab[xn], ap[xn], az[xn], am[xn],
hb[xn], hp[xn], hz[xn], hm[xn], // h?[] and t?[] are not available for i that a[i] == '+' || a[i] == '*'
tb[xn], tp[xn], tz[xn], tm[xn];
__int64 INV(__int64 x)
{
__int64 r = ;
for (__int64 b = MOD - ; b; b >>= )
{
if (b & )
r = r * x % MOD;
x = x * x % MOD;
}
return r;
}
__int64 F(int l, int r)
{
if (a[l] == '+' || a[l] == '*' || a[l] == ')')
return -;
if (a[r] == '+' || a[r] == '*' || a[r] == '(')
return -;
if (sb[pb[l]] != sb[r])
return -;
int lep = pp[l], rip = sp[r];
if (sp[lep] != rip)
return (hb[r] + tb[l] - ab[pb[l]] + MOD) % MOD;
else
{
int lem = pm[l], rim = sm[r];
if (sm[lem] != rim)
return hz[r] + tz[l] == az[pp[l]] ? hp[r] * tp[l] % MOD * INV(ap[pp[l]]) % MOD : ;
else
return (hm[r] + (tm[l] - am[pm[l]] + MOD) * iP10[rim - r - ]) % MOD;
}
return ;
}
int main()
{
scanf("%s", a + );
while (a[N + ])
N++;
N += ;
a[] = '(', a[N] = ')';
iP10[] = P10[] = ;
for (int i = ,l; i <= N; i++)
{
P10[i] = P10[i - ] * % MOD;
iP10[i] = iP10[i - ] * % MOD;
}
for (i = ; i <= N; i++)
{
if( a[i] == ')')
{
ab[Lb[D]] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
ap[Lp[D]] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
az[Lp[D]] = Az[D] + !Am[D];
am[Lm[D]] = Am[D];
}
pb[i] = Lb[D];
pp[i] = Lp[D];
pm[i] = Lm[D];
if (a[i] == '(')
{
D++;
Lb[D] = Lp[D] = Lm[D] = i;
Az[D] = Ab[D] = Am[D] = ;
Ap[D] = ;
}
else if (a[i] == '+')
{
ap[Lp[D]] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
az[Lp[D]] = Az[D] + !Am[D];
am[Lm[D]] = Am[D];
Lp[D] = Lm[D] = i;
Ab[D] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
Ap[D] = ;
Az[D] = ;
Am[D] = ;
}
else if (a[i] == '*')
{
am[Lm[D]] = Am[D];
Lm[D] = i;
Ap[D] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
Az[D] = Az[D] + !Am[D];
Am[D] = ;
}
else if (a[i] >= '' && a[i] <= '')
{
Am[D] = (Am[D] * + a[i] - ) % MOD;
hb[i] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
hp[i] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
hz[i] = Az[D] + !Am[D];
hm[i] = Am[D];
}
else
{
Am[D - ] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
D--;
hb[i] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
hp[i] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
hz[i] = Az[D] + !Am[D];
hm[i] = Am[D];
}
}
for (i = N, l = -; i; i--)
{
if (a[i] >= '' && a[i] <= '')
l++;
else
l = -;
sb[i] = Lb[D];
sp[i] = Lp[D];
sm[i] = Lm[D];
if (a[i] == ')')
{
D++;
Lb[D] = Lp[D] = Lm[D] = i;
Az[D] = Ab[D] = Am[D] = ;
Ap[D] = ;
}
else if (a[i] == '+')
{
Lp[D] = Lm[D] = i;
Ab[D] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
Ap[D] = ;
Az[D] = ;
Am[D] = ;
}
else if (a[i] == '*')
{
Lm[D] = i;
Ap[D] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
Az[D] = Az[D] + !Am[D];
Am[D] = ;
}
else if (a[i] >= '' && a[i] <= '')
{
Am[D] = (Am[D] + P10[l] * (a[i] - )) % MOD;
tb[i] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
tp[i] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
tz[i] = Az[D] + !Am[D];
tm[i] = Am[D];
}
else
{
Am[D - ] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
D--;
tb[i] = (Ab[D] + (Az[D] ? : Ap[D]) * Am[D]) % MOD;
tp[i] = Ap[D] * (Am[D] ? Am[D] : ) % MOD;
tz[i] = Az[D] + !Am[D];
tm[i] = Am[D];
}
}
for (scanf("%d", &Q); Q--; )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%I64d\n", F(l + , r + ));
}
return ;
}