zoj3929
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define N 100005
const int MOD=1000000007;
typedef long long ll;
int two[N];
int pos[N];
int tree[N];
int n;
inline int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
for(int i=x;i<=n;i+=lowbit(i)){
tree[i]+=y;
if(tree[i]>=MOD) tree[i]-=MOD;
}
}
int sum(int x){
int an=0;
for(int i=x;i>=1;i-=lowbit(i)){
an+=tree[i];
if(an>=MOD) an-=MOD;
}
return an;
}
int main(){
int T;
int i,j,k;
scanf("%d",&T);
two[0]=1; for(i=1;i<=100000;i++) two[i]=(two[i-1]*2)%MOD;
while(T--){
ll ans=0;
scanf("%d",&n);
memset(tree,0,sizeof(tree));
for(i=1;i<=n;i++) scanf("%d",&pos[i]);
for(i=1;i<=n;i++){
ans=( ans+(ll)( sum(n)-sum(pos[i])+MOD )*two[n-i] )%MOD;
ans=( ans+(ll)( sum(pos[i]-1) )*two[n-i] )%MOD;
if(i==1) add(pos[i],2);
else add(pos[i],two[i-1]);
}
printf("%lld
",ans);
}
return 0;
}
/*
【题意】
一个双端队列 依次将带标号的球等概率从左或右放入
求 xi > xi+1 的i的数量 的方案数
【做法】
树状数组维护
每次加上该球
1.从左边进入 恰好它旁边的球比它小的方案数
2.从右边进入 恰好它旁边的球比它大的方案数
【思考】
*/
zoj3930
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define INF 0x3f3f3f3f
const int MOD =1000000007;
typedef long long ll;
char t[2005];
char a[2005];
vector<char> vc;
int cn;
int main(){
int T;
int i,j,k;
int cn;
scanf("%d",&T); getchar();
while(T--){
vc.clear();
gets(t); int len=strlen(t);
for(i=0;i<len;i++){
if( t[i]==' ' || t[i]==' ' ) continue;
else if( t[i]>='0' && t[i]<='9' ) vc.push_back(t[i]);
else if(t[i]=='d'){
for(cn=0,j=i+1;j<len;j++){
if( t[j]>='0' && t[j]<='9' ) a[cn++]=t[j];
else break;
}
a[cn]=' ';
i=j-1;
ll tmp=0;
for(j=0;j<vc.size();j++){
tmp=tmp*10+vc[j]-'0';
} vc.clear();
if(tmp<=1) {
printf("[d%s]",a);
}else {
printf("(");
while(tmp--){
printf("[d%s]",a);
if(tmp) printf(" + ");
}
printf(")");
}
}else if( t[i]=='+' || t[i]=='*' || t[i]=='-' || t[i]=='/' ){
for(j=0;j<vc.size();j++) printf("%c",vc[j]); vc.clear();
printf(" %c ",t[i]);
}else {
for(j=0;j<vc.size();j++) printf("%c",vc[j]); vc.clear();
printf("%c",t[i]);
}
}
for(j=0;j<vc.size();j++) printf("%c",vc[j]); vc.clear();
printf(" = [Result]
");
}
return 0;
}
/*
【题意】
将一段字符串进行处理
1.删去空格和tab键(' ') 坑点
2.将3d5转换为[d5] + [d5] + [d5]
3.在运算符两边加上空格
【做法】
模拟 注意' '坑点
【思考】
比赛时应该耐心看完每个题 这个题之前没人做 最后才被人发现是水题
*/
zoj3931
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
int S;
int F[150];
map<ll,int> mp[2];
map<ll,int>::iterator it;
priority_queue<int,vector<int>,greater<int> >Q;
struct Node{
ll l,r;
}tree[150];
int main(){
int T;
int i,j,k;
ll target;
scanf("%d",&T);
while(T--){
while(!Q.empty()) Q.pop();
for(i=0;i<2;i++) mp[i].clear();
scanf("%d",&S);
for(i=0;i<S;i++) scanf("%d",&F[i]);
scanf("%lld",&target);
for(i=0;i<S;i++) {
Q.push(F[i]);
}
int cn1=0;
while(Q.size()>1){
int t1=Q.top(); Q.pop();
int t2=Q.top(); Q.pop();
Q.push(t1+t2);
tree[++cn1].l=t1; tree[cn1].r=t2;
}
int flag=1;
mp[flag][tree[1].l]=1; mp[flag][tree[1].r]=1;
for(i=2;i<=cn1;i++){
mp[flag^1].clear();
for(it=mp[flag].begin();it!=mp[flag].end();it++){
ll t1=it->first;
if( t1+tree[i].l<=target ) mp[flag^1][t1+tree[i].l]=1;
if( t1+tree[i].r<=target ) mp[flag^1][t1+tree[i].r]=1;
}
flag^=1;
}
if(mp[flag][target]) printf("Yes
");
else printf("No
");
}
return 0;
}、
/*
【题意】
对于给出的序列进行哈夫曼建树
求是否有方案树满足 每个数的编码中 0 的个数合为 E
【做法】
模拟
【思考】
这个题当时也是没时间看 全卡在那道zkw费用流上了
*/
zoj3933
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;
const int MAXN=505;
const int MAXM=250005;
const int INF=0x3f3f3f3f;
struct Edge{
int to,next,cap,flow,cost;
Edge(int _to=0,int _next=0,int _cap=0,int _flow=0,int _cost=0):
to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost){}
}edge[MAXM];
vector<pair<int,int> > vc;
struct ZKW_MinCostMaxFlow{
int head[MAXN],tot;
int cur[MAXN];
int dis[MAXN];
bool vis[MAXN];
int ss,tt,N;
int min_cost,max_flow;
void init(){
tot=0;
vc.clear();
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost){
edge[tot]=Edge(v,head[u],cap,0,cost);
head[u]=tot++;
edge[tot]=Edge(u,head[v],0,0,-cost);
head[v]=tot++;
}
int aug(int u,int flow){
if(u==tt) return flow;
vis[u]=true;
for(int i=cur[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if( edge[i].cap>edge[i].flow && !vis[v] && dis[u]==dis[v]+edge[i].cost ){
int tmp=aug(v,min(flow,edge[i].cap-edge[i].flow));
edge[i].flow+=tmp;
edge[i^1].flow-=tmp;
cur[u]=i;
if(tmp) return tmp;
}
}
return 0;
}
bool modify_label(){
int d=INF;
for(int u=0;u<N;u++){
if(vis[u])
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>edge[i].flow && !vis[v])
d=min(d,dis[v]+edge[i].cost-dis[u]);
}
}
if(d==INF) return false;
for(int i=0;i<N;i++)
if(vis[i]){
vis[i]=false;
dis[i]+=d;
}
return true;
}
void mincostmaxflow(int start,int ed,int n){
ss=start,tt=ed,N=n;
min_cost=max_flow=0;
for(int i=0;i<n;i++) dis[i]=0;
while(1){
for(int i=0;i<n;i++) cur[i]=head[i];
while(1){
for(int i=0;i<n;i++) vis[i]=false;
int tmp=aug(ss,INF);
if(tmp==0) break;
max_flow+=tmp;
min_cost+=tmp*dis[ss];
}
if(!modify_label()) break;
}
printf("%d %d
",max_flow,2*max_flow-min_cost);
}
void prin(int x,int y){
int i,j;
for(i=1;i<=x;i++){
for(j=head[i];j!=-1;j=edge[j].next){
if(edge[j].flow==1){
vc.push_back(make_pair(i,edge[j].to)); break;
}
}
}
}
}solve;
char s1[505];
char s2[505];
int num[505];
int pre[505];
int bad[505][505];
int main(){
int T;
int n;
int i,j,k;
scanf("%d",&T);
while(T--){
solve.init();
memset(bad,0,sizeof(bad));
int a1=0; int a2=0;
scanf("%d %s %s",&n,&s1,&s2);
for(i=0;s1[i];i++){
if(s1[i]=='1') a1++;
else a2++;
}
int b1=0; int b2=a1;
for(i=0;s1[i];i++){
if(s1[i]=='1') num[i]=++b1,pre[b1]=i;
else num[i]=++b2,pre[b2]=i;
}
for(i=0;i<n;i++){
int a,b; scanf("%d",&a);
for(j=0;j<a;j++){
scanf("%d",&b); bad[i][b-1]=1;
}
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++){
if(bad[i][j]==0){
int t1=num[i]; int t2=num[j];
if(s1[i]==s1[j]) continue;
if(t1>t2) swap(t1,t2);
solve.addedge( t1,t2,1,(s2[i]=='1')+(s2[j]=='1') );
}
}
for(i=1;i<=a1;i++) solve.addedge(0,i,1,0);
for(i=a1+1;i<=n;i++) solve.addedge(i,n+1,1,0);
solve.mincostmaxflow(0,n+1,n+2);
solve.prin(a1,n);
for(i=0;i<vc.size();i++){
int t1=vc[i].first; int t2=vc[i].second;
printf("%d %d
",pre[t1]+1,pre[t2]+1);
}
}
return 0;
}
/*
【题意】
有两组人 给出他们的性别和各自不喜欢的人
要求从两组各选出一个人成为一队
求最多能组成的队数 以及最多的女生的情况
【做法】
zkw费用流 用KM以及SPFA被卡的不要不要的
两组放两边 二分建图
【思考】
*/