1、Quasi-palindrome
1003 拍照
思路：先把所有的线条在x轴上可观察到的地方求出来，起源和顶峰对应数组a里的x,y，排序后从坐标最小开端枚举。即使赶上源点标志，就加一（表明从那个职位上马可先生以望见）；截至点注脚减一（表明从那几个岗位上马不可知）。还有一个值得注意的是：唯有向左行驶的船舶可知坐标大于向右行驶的船只，才可能在某个时刻同时出现在照片里
/**************************************************************
Problem:hdu 5417
User: youmi
Language: C++
Result: Accepted
Time:1591MS
Memory:1816K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
const int maxn=20000+10;
int n,cnt,x,y,z,d,po,lmax,l,r,ans;
struct data
{
int x,y,z;
}a[maxn];
bool cmp(data a,data b)
{
if (a.x!=b.x) return a.x<b.x;
else
{
if (a.y!=b.y) return a.y<b.y; else return a.z<b.z;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T_T;
scanf("%d",&T_T);
for(int kase=1;kase<=T_T;kase++)
{
n=read(); cnt=0;
for (int i=1;i<=n;i++)
{
x=read(),y=read(),z=read(),d=read();
if (y-x<=2*z)
{
if (d==1) po=0; else po=1;
a[++cnt].x=y-z; a[cnt].y=0; a[cnt].z=po;
a[++cnt].x=x+z; a[cnt].y=1; a[cnt].z=po;
}
}
sort(a+1,a+cnt+1,cmp);
lmax=l=r=ans=0;
for (int i=1;i<=cnt;i++)
{
if (a[i].z==0)
{
if (a[i].y==0) ++l; else --l;
}
else
{
if (a[i].y==0) ++r; else --r;
}
if (l>lmax) lmax=l;
if (lmax+r>ans) ans=lmax+r;
}
printf("Case #%d:\n%d\n",kase,ans);
}
return 0;
}
View Code
2016″百度之星” – 初赛（Astar
Round2B）
思路：先选出[l,r]距离内的矮小值，然后枚举[l,r]内的所以值，就足以算出以a[p]为最小值的富有区间的【区间的价值】了；不过有少数需求小心：在以a[p]为
最小值时，统计出的【区间大小大于等于3】（要是间隔大小为k）的【区间的价值】，应该是距离大小为[2,k]内的最大值。
/**************************************************************
Problem:hdu 5696
User: youmi
Language: C++
Result: Accepted
Time:1419MS
Memory:4484K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);
using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
char c; int flag = 1;
for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0';
for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag;
}
int Pow(int base, ll n, int mo)
{
if (n == 0) return 1;
if (n == 1) return base % mo;
int tmp = Pow(base, n >> 1, mo);
tmp = (ll)tmp * tmp % mo;
if (n & 1) tmp = (ll)tmp * base % mo;
return tmp;
}
//***************************
int n;
const int maxn=200000+10;
int a[maxn];
ll ans[maxn];
ll temp[maxn];
void sovle(int l,int r)
{
if(r<l)
return ;
int p=0;
int len=(r-l+1);
rep(i,0,len)
temp[i]=0;
rep(i,l,r)
{
if(a[i]<a[p])
p=i;
}
rep(i,l,p)
temp[p-l+1]=Max(temp[p-l+1],1ll*a[p]*a[i]);
rep(i,p,r)
temp[r-p+1]=Max(temp[r-p+1],1ll*a[p]*a[i]);
rep(i,3,len)
temp[i]=Max(temp[i],temp[i-1]);
rep(i,1,len)
ans[i]=Max(ans[i],temp[i]);
sovle(l,p-1);
sovle(p+1,r);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while(~sc(n))
{
a[0]=oo;
rep(i,1,n)
sc(a[i]);
zeros(ans);
sovle(1,n);
rep(i,1,n)
ptlld(ans[i]);
}
}
View Code
思路：C（n-2,n+m-4）;
思路：对区间起末坐标存入数组排序，然后枚举，蒙受源点存入队列，碰到末点更新答案。下边是具体做法：
用y数组记录下各类区间的id,l,r；并用x数组记录下区间的id，区间起（末）坐标并标记为起（末）；对x数组举办排序，然后一一枚举x数组并将符号为先导点的坐标压入队列，那里的队列用数组完毕。当然这一个历程大家必要多个数组：index用来标记队列中点对应的间距id,pt用来标记区间id对应队列中的地方。如若为起头点，那么大家直接压入队列就好了。若是为末点，大家就得处理他。
拍卖操作：
- 第一，倘若队列元素个数小于k，直接把队列中id对应的职分弹出去就好了，大家那里是符号为-1；
- 假若个数大于等于k，大家就创新答案。因为我们早已对x排序过，所以先进行列的开局坐标值肯定更小；而我辈只需求k个区间交就可以了，所以大家取队列中的第k个值来测算。那里第k个值所对应队列中的地方我们用flag记录。
- 若是当前处理的id在队列中的位置在flag后边，那么flag指向的是k-1个区间交的地方，所以我们要不停向后搜索。因为被弹骑行列的岗位都被标记为-1,所以while循环到非-1就是眼下的k个区间交对应的职位。
/**************************************************************
Problem:hdu 5700
User: youmi
Language: C++
Result: Accepted
Time:1996MS
Memory:7208K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);
using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
char c; int flag = 1;
for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0';
for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag;
}
int Pow(int base, ll n, int mo)
{
if (n == 0) return 1;
if (n == 1) return base % mo;
int tmp = Pow(base, n >> 1, mo);
tmp = (ll)tmp * tmp % mo;
if (n & 1) tmp = (ll)tmp * base % mo;
return tmp;
}
//***************************
int n,k,m;
const int maxn=100000+10;
int a[maxn];
ll sum[maxn];
struct T
{
int id,l,r;
void init(int _id,int _l,int _r)
{
id=_id,l=_l,r=_r;
}
}y[maxn];
struct Y
{
int id,p,dir;
void init(int _id,int _p,int _dir)
{
id=_id,p=_p,dir=_dir;
}
}x[maxn<<1];
bool cmp(struct Y b,struct Y c)
{
if(b.p==c.p)
return b.dir<c.dir;
return b.p<c.p;
}
int index[maxn];
int pt[maxn];
void sovle()
{
ll ans=0;
zeros(pt);
zeros(index);
int head=1,sz=0,flag=-1;
rep(i,1,2*m)
{
if(x[i].dir==0)
{
index[head]=x[i].id;
pt[x[i].id]=head;
head++,sz++;
if(sz==k)
flag=head-1;
}
else
{
if(sz>=k)
{
ans=Max(ans,sum[x[i].p]-sum[y[index[flag]].l-1]);
if(pt[x[i].id]<=flag&&sz-1>=k)
{
flag++;
while(index[flag]==-1&&flag<=head)
{
flag++;
}
}
}
sz--;
index[pt[x[i].id]]=-1;
}
}
ptlld(ans);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while(~sc3(n,k,m))
{
rep(i,1,n)
sc(a[i]);
sum[0]=0;
sum[1]=a[1];
rep(i,2,n)
sum[i]=sum[i-1]+a[i];
int l,r;
rep(i,1,m)
{
sc2(l,r);
x[i*2-1].init(i,l,0);
x[i*2].init(i,r,1);
y[i].init(i,l,r);
}
sort(x+1,x+1+2*m,cmp);
sovle();
}
}
View Code
思路：那个题材可分类为01分数规划里总括果了，所以已经链接到那篇博文了
2016″百度之星” – 初赛（Astar
Round2A）
1001 ALL X
思路：x*(10n-1)/9，之后的应当就大致了
1002 Sitting in Line
其一已经再博客里写过了，所以把标题已经连续到写的丰盛博客了
思路：那些题要求一个子树里的最大值。先dfs三次整棵树，并且记下一个点进去时候的id和出去的id，那么这八个id之间就是那几个点的子树了。然后利用线段树处理一下，nlogn复杂度
/**************************************************************
Problem:hdu 5692
User: youmi
Language: C++
Result: Accepted
Time:2355MS
Memory:14932K
****************************************************************/
#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ctime>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);
using namespace std;
typedef long long ll;
ll n,m;
ll z,x,y;
const int maxn=100000+10;
int in[maxn],out[maxn];
ll val[maxn];
ll dp[maxn];
int head[maxn];
int T=0,id;
struct side
{
int v,next;
}e[maxn];
struct segment
{
int l,r;
ll mx,cg;
void init(ll a,ll b,ll c,ll d)
{
l=a,r=b,mx=c,cg=d;
}
}seg[maxn<<2];
inline ll read()
{
ll x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void init()
{
T=0;
id=0;
ones(head);
}
void build(int u,int v)
{
e[T].v=v;
e[T].next=head[u];
head[u]=T++;
}
void dfs(int u,int f,ll c)
{
in[u]=++id;
if(u==0)
dp[id]=c;
else
dp[id]=dp[in[f]]+c;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v!=f)
dfs(v,u,val[v]);
}
out[u]=id;
}
void pushup(int step)
{
seg[step].mx=Max(seg[lson].mx,seg[rson].mx);
}
void pushdown(int step)
{
seg[lson].mx+=seg[step].cg;
seg[rson].mx+=seg[step].cg;
seg[lson].cg+=seg[step].cg;
seg[rson].cg+=seg[step].cg;
seg[step].cg=0;
}
void build(int step,int l,int r)
{
seg[step].init(l,r,0,0);
if(l==r)
{
seg[step].init(l,r,dp[l],0);
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(step);
}
void update(int step,int l,int r,ll c)
{
if(seg[step].l==l&&seg[step].r==r)
{
seg[step].cg+=c;
seg[step].mx+=c;
return ;
}
pushdown(step);
int mid=(seg[step].l+seg[step].r)>>1;
if(l>mid)
update(rson,l,r,c);
else if(mid>=r)
update(lson,l,r,c);
else
{
update(lson,l,mid,c);
update(rson,mid+1,r,c);
}
pushup(step);
}
ll query(int step,int l,int r)
{
if(seg[step].l==l&&seg[step].r==r)
{
return seg[step].mx;
}
pushdown(step);
int mid=(seg[step].l+seg[step].r)>>1;
if(l>mid)
return query(rson,l,r);
else if(mid>=r)
return query(lson,l,r);
else
{
ll temp=query(lson,l,mid);
temp=Max(temp,query(rson,mid+1,r));
return temp;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T_T;
scanf("%d",&T_T);
for(int kase=1;kase<=T_T;kase++)
{
printf("Case #%d:\n",kase);
n=read(),m=read();
ll u,v;
init();
rep(i,1,n-1)
{
u=read(),v=read();
build(u,v);
build(v,u);
}
rep(i,0,n-1)
{
u=read();
val[i]=u;
}
dfs(0,-1,val[0]);
build(1,1,n);
rep(i,1,m)
{
z=read(),x=read();
if(z==1)
ptlld(query(1,in[x],out[x]));
else
{
y=read();
ll temp=y-val[x];
update(1,in[x],out[x],temp);
val[x]+=temp;
}
}
}
return 0;
}
View Code
题意：问一个字符串（你可以添加前导‘0’或不丰裕）是或不是是回文串
1005 BD String
思路：
1—B
2—BBD
3—BBD|B|BDD
4—BBD|B|BDD|B|BBD|D|BDD
5—BBD|B|BDD|B|BBD|D|BDD|B|BBD|B|BDD|D|BBD|D|BDD
从第五行可观察规律：每8个为一组，其中BBD,BDD延续重复；4的倍数上相应的假名，又是题给规律的产出，那么那有的开展dfs即可；然后对于小于等于8的片段，可以用一个数组预处理。
小心：（小于等于8的片段）与（4的翻番）在岗位为4的地点重复统计了一遍，所以要去掉这一片段
/**************************************************************
Problem:hdu 5694
User: youmi
Language: C++
Result: Accepted
Time:0MS
Memory:1572K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);
using namespace std;
typedef long long ll;
inline ll read()
{
ll x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int b[]={0,1,2,2,0,3,3,3,0};
ll sovle(ll tt)
{
if(tt==0)
return 0;
ll ans=0;
ans+=sovle(tt/4);
if(tt<4)
return b[tt];
else if(tt<8)
{
if(tt==4)
return ans+b[3];
else
return ans+b[tt];
}
ans+=3*(tt/8);
ans+=sovle(tt%8);
if(tt%8>=4)
ans-=1;
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T_T;
scanf("%d",&T_T);
for(int kase=1;kase<=T_T;kase++)
{
ll l,r;
l=read(),r=read();
ll ans=sovle(r);
ans-=sovle(l-1);
ptlld(ans);
}
}
View Code
1006 Gym Class
其一贪得无厌+拓扑就足以了，所以那里也一向把链接给到对应博客了
思路：将加以的字符串的前缀‘0’和后缀‘0’都去掉，然后看其是不是为回文串
1 #include<iostream>
2 using namespace std;
3 int main()
4 {
5 int num;
6 scanf("%d", &num);
7 while (num / 10 != 0 && num % 10 == 0) num /= 10;
8 int tmp = 0;
9 int tnum = num;
10 while (tnum)
11 {
12 tmp = tmp * 10 + tnum % 10;
13 tnum /= 10;
14 }
15 if (tmp == num) printf("YES\n");
16 else printf("NO\n");
17
18 return 0;
19 }
View Code
2、Kayaking
题意：给出2*n个人的体重，有n-1辆双人车和2辆单人车，问每辆双人车上五个人的体重之差的和微小是有点
思路：先把体重从小到大排序，然后枚举不坐双人车的多少人，算出剩下的人的小小体重差的和，取最小值。
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 int wt[120];
5 const int INF = 1e9;
6 int main()
7 {
8 int n;
9 scanf("%d", &n);
10 for (int i = 1; i <= 2 * n; i++)
11 {
12 scanf("%d", &wt[i]);
13 }
14 sort(wt + 1, wt + 2 * n + 1);
15
16 int sum = INF;
17 for (int i = 1; i < 2 * n; i++)
18 {
19 for (int j = i + 1; j <= 2 * n; j++)
20 {
21 int tsum = 0;
22 for (int k = 1; k <= 2 * n;)
23 {
24 while(k == i||k==j)
25 {
26 k++;
27 }
28 int w1 = wt[k];
29 k++;
30 while(k == j||k==i)
31 {
32 k++;
33 }
34 tsum += wt[k] - w1;
35 k++;
36 }
37 sum = min(sum, tsum);
38 }
39 }
40 printf("%d\n", sum);
41 return 0;
42 }
View Code
3、1-2-3
题意：给出Iris和鲍勃的出拳依据及他们先是次的出拳，问k轮后Iris和鲍伯的得分
思路：找到循环节。
1 #include<iostream>
2 #include<map>
3 using namespace std;
4 int alice[3][3];
5 int bob[3][3];
6 map<pair<int, int>, int>mp;
7 map<int, pair<int, int> >score;
8 int a, b;
9 long long k;
10 int main()
11 {
12 scanf("%I64d%d%d", &k, &a, &b);
13 for (int i = 0; i < 3; i++)
14 {
15 for (int j = 0; j < 3; j++)
16 {
17 scanf("%d", &alice[i][j]);
18 alice[i][j]--;
19 }
20 }
21 for (int i = 0; i < 3; i++)
22 {
23 for (int j = 0; j < 3; j++)
24 {
25 scanf("%d", &bob[i][j]);
26 bob[i][j]--;
27 }
28 }
29 int apoint = 0, bpoint = 0;
30 int prea, preb;
31 int kk = 0;
32 int T,ta,tb,st;
33 a--, b--;
34 while (kk < k)
35 {
36 if (kk == 0)
37 {
38 prea = a;
39 preb = b;
40 if (a == 0 && b == 2|| a== 2 && b == 1||a==1&&b==0) apoint++;
41 else if (b == 0 && a == 2 || b == 2 && a == 1 || b == 1 && a == 0)bpoint++;
42 mp[make_pair(a, b)] = ++kk;
43 }
44 else
45 {
46 int aa = alice[prea][preb], bb = bob[prea][preb];
47 if (st=mp[make_pair(aa, bb)])
48 {
49 T = kk - st + 1;
50 pair<int, int>t1, t2;
51 if (T == 1)
52 {
53 t1 = score[st];
54 if (st > 1)
55 {
56 t2 = score[st - 1];
57 ta = t1.first - t2.first;
58 tb = t1.second - t2.second;
59 }
60 else
61 {
62 ta = t1.first, tb = t1.second;
63 }
64 }
65 else
66 {
67 if (st > 1)
68 {
69 t1 = score[st - 1];
70 t2 = score[kk];
71 ta = t2.first - t1.first;
72 tb = t2.second - t1.second;
73 }
74 else
75 {
76 t1 = score[kk];
77 ta = t1.first, tb = t1.second;
78 }
79 }
80 break;
81 }
82 if (aa == 0 && bb == 2 || aa == 2 && bb == 1 || aa == 1 && bb == 0) apoint++;
83 else if (bb == 0 && aa == 2 || bb == 2 && aa == 1 || bb == 1 && aa == 0)bpoint++;
84 mp[make_pair(aa, bb)] = ++kk;
85 prea = aa, preb = bb;
86 }
87 score[kk] = make_pair(apoint, bpoint);
88 }
89 if (kk == k) printf("%d %d\n", apoint, bpoint);
90 else
91 {
92 long long suma = 0, sumb = 0;
93 if (st == 1) suma += 1ll*k / T*ta, sumb += 1ll*k / T*tb;
94 else
95 {
96 pair<int, int>tmp = score[st - 1];
97 suma += tmp.first, sumb += tmp.second;
98 k -= st-1;
99 suma += 1ll * k / T*ta, sumb += 1ll * k / T*tb;
100 }
101 if (k%T)
102 {
103 if (st == 1)
104 {
105 pair<int, int>t = score[k%T];
106 suma += t.first, sumb += t.second;
107 }
108 else
109 {
110 pair<int, int>t1 = score[st-1];
111 pair<int, int>t2 = score[k%T+st-1];
112 suma += t2.first - t1.first, sumb += t2.second - t1.second;
113 }
114 }
115 printf("%I64d %I64d\n", suma, sumb);
116 }
117 return 0;
118 }
View Code
4、Yet Another Array Queries
Problem
题意：对数组进行两种操作：1是将某个区间内的数左移（最右边移到的移到最右边）；2是将某个区间内的数反转。给出初阶数组和若干操作后，问若干下标地点的数是什么人
思路：对每一个所精晓的底下的数，从最终三回操作向前找其相应的起初数组的下标。
1 #include<iostream>
2 using namespace std;
3 int a[200010];
4 struct node
5 {
6 int ff;
7 int ll;
8 int rr;
9 }qq[200010];
10 int main()
11 {
12 int n, q, m;
13 scanf("%d%d%d", &n, &q, &m);
14 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
15 for (int i = 1; i <= q; i++) scanf("%d%d%d", &qq[i].ff, &qq[i].ll, &qq[i].rr);
16 for (int i = 1; i <= m; i++)
17 {
18 int pos;
19 scanf("%d", &pos);
20 for (int j = q; j >= 1; j--)
21 {
22 if (pos >= qq[j].ll&&pos <= qq[j].rr)
23 {
24 if (qq[j].ff == 1)
25 {
26 if (pos > qq[j].ll) pos--;
27 else pos = qq[j].rr;
28 }
29 else
30 {
31 pos = qq[j].rr - (pos - qq[j].ll);
32 }
33 }
34 }
35 if (i > 1) printf(" ");
36 printf("%d", a[pos]);
37 }
38 printf("\n");
39 return 0;
40 }
View Code
5、Turn Off The TV
题意：有好三个区间，现在亟待确定是还是不是有结余的区间，使得在去掉这一个区间后本来至少被一个间隔覆盖的总长度不会回落。若存在，输出任意一个满足条件的间距的数码。
思路：把区间按左端点排序，假如当前距离的右端点小于等于当前的最右端，则该距离就是剩下区间；否则，假如当前距离的左端点比当下最右端还要大，则更新当前距离最左端和眼前距离最右端；否则，假使当前距离的下一个间隔和当下最左端和最右端构成的间距可以覆盖当前距离，则当前距离就是剩下区间。
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 struct node
5 {
6 int ll;
7 int rr;
8 int idx;
9 }tv[200010];
10 bool Cmp(const node&a, const node&b)
11 {
12 if (a.ll == b.ll) return a.rr > b.rr;
13 else return a.ll < b.ll;
14 }
15 int main()
16 {
17 int n;
18 scanf("%d", &n);
19 for (int i = 0; i < n; i++)
20 {
21 scanf("%d%d", &tv[i].ll, &tv[i].rr);
22 tv[i].idx = i + 1;
23 }
24 sort(tv, tv + n, Cmp);
25 int ans = -1;
26 int tl = tv[0].ll, tr = tv[0].rr;
27 for (int i = 1; i < n; i++)
28 {
29 if (tv[i].rr <= tr)
30 {
31 ans = i;
32 break;
33 }
34 else if (tv[i].ll > tr)
35 {
36 tl = tv[i].ll;
37 tr = tv[i].rr;
38 }
39 else
40 {
41 if (i + 1 < n&&tv[i + 1].ll <= tr+1&&tv[i + 1].rr >= tv[i].rr)
42 {
43 ans = i;
44 break;
45 }
46 else
47 {
48 tl = tv[i].ll;
49 tr = tv[i].rr;
50 }
51 }
52 }
53 if (ans == -1) printf("-1\n");
54 else printf("%d\n", tv[ans].idx);
55 return 0;
56 }
View Code
6、Almost Permutation
题意：你现在明白多少间隔内的数是过量等于某一个数或者小于等于某一个数，然后定义cost为数组中每个数现身的次数的平方和，问最小的cost.
思路：最小开支最大流。当有着条件都严丝合缝时（没有争持），将起点和各类index相连，容量为1，开支为0；将每个index和该index可以填的数字不断，容量为1，开支为0；对于每个数字，和汇点连n条边，容量1，开支为1、3、5、……、n*n-(n-1)(n-1)(假使当前以此数字出现k次，则须求向汇点连k条边，由于纤维开支，肯定取最小费用的k条，由于前x条花费之和=x^2,即标题所要求的)
1 #include<iostream>
2 #include<algorithm>
3 #include<queue>
4 #include<cstring>
5 using namespace std;
6 int maxlv[55];
7 int minlv[55];
8 int cnt[55];
9 struct pp
10 {
11 int l;
12 int r;
13 int len;
14 }p[55];
15
16 //最小费用最大流模板
17 #define MAXN 120
18 #define MAXM (2500*2+50)*2+100
19 #define INF 0x3f3f3f3f
20 using namespace std;
21 struct Edge
22 {
23 int from, to, cap, flow, cost, next;
24 Edge(int fr = 0, int tt = 0, int ca = 0, int fl = 0, int ct = 0, int nt = 0) :from(fr), to(tt), cap(ca), flow(fl), cost(ct), next(nt)
25 {
26 };
27 };
28 Edge edge[MAXM];
29 int Head[MAXN], edgenum;
30 int pre[MAXN];//记录增广路径上 到达点i的边的编号
31 int dist[MAXN];
32 bool vis[MAXN];
33 int N;//点数
34 //int M;//边数
35 int source, sink;//超级源点 超级汇点
36 void init(int numnode,int st,int sk)
37 {
38 N = numnode, source = st, sink = sk;
39 edgenum = 0;
40 memset(Head, -1, sizeof(Head));
41 }
42 void addEdge(int u, int v, int w, int c)
43 {
44 //Edge E1 = { u, v, w, 0, c, head[u] };
45 //edge[edgenum] = E1;
46 edge[edgenum] = Edge(u, v, w, 0, c, Head[u]);
47 Head[u] = edgenum++;
48 //Edge E2 = { v, u, 0, 0, -c, head[v] };
49 //edge[edgenum] = E2;
50 edge[edgenum] = Edge(v, u, 0, 0, -c, Head[v]);
51 Head[v] = edgenum++;
52 }
53 bool SPFA(int s, int t)//寻找花销最少的路径
54 {
55 //跑一遍SPFA 找s——t的最少花销路径 且该路径上每一条边不能满流
56 //若存在 说明可以继续增广，反之不能
57 queue<int> Q;
58 memset(dist, INF, sizeof(dist));
59 memset(vis, false, sizeof(vis));
60 memset(pre, -1, sizeof(pre));
61 dist[s] = 0;
62 vis[s] = true;
63 Q.push(s);
64 while (!Q.empty())
65 {
66 int u = Q.front();
67 Q.pop();
68 vis[u] = false;
69 for (int i = Head[u]; i != -1; i = edge[i].next)
70 {
71 Edge E = edge[i];
72 if (dist[E.to] > dist[u] + E.cost && E.cap > E.flow)//可以松弛 且 没有满流
73 {
74 dist[E.to] = dist[u] + E.cost;
75 pre[E.to] = i;//记录前驱边 的编号
76 if (!vis[E.to])
77 {
78 vis[E.to] = true;
79 Q.push(E.to);
80 }
81 }
82 }
83 }
84 return pre[t] != -1;//可达返回true
85 }
86 void MCMF(int s, int t, int &cost, int &flow)
87 {
88 flow = 0;//总流量
89 cost = 0;//总费用
90 while (SPFA(s, t))//每次寻找花销最小的路径
91 {
92 int Min = INF;
93 //通过反向弧 在源点到汇点的最少花费路径 找最小增广流
94 for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
95 {
96 Edge E = edge[i];
97 Min = min(Min, E.cap - E.flow);
98 }
99 //增广
100 for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
101 {
102 edge[i].flow += Min;
103 edge[i ^ 1].flow -= Min;
104 cost += edge[i].cost * Min;//增广流的花销
105 }
106 flow += Min;//总流量累加
107 }
108 }
109
110 int main()
111 {
112 int n,q;
113 scanf("%d%d", &n, &q);
114 for (int i = 1; i <= n; i++) maxlv[i] = n, minlv[i] = 1;
115 bool flag = true;
116 for (int i = 1; i <= q; i++)
117 {
118 int type, li, ri, vi;
119 scanf("%d%d%d%d", &type, &li, &ri, &vi);
120 if (!flag)continue;
121 if (type == 1)
122 {
123 for (int j = li; j <= ri; j++)
124 {
125 if (minlv[j] < vi) minlv[j] = vi;
126 if (minlv[j] > maxlv[j])
127 {
128 flag = false;
129 break;
130 }
131 }
132 }
133 else
134 {
135 for (int j = li; j <= ri; j++)
136 {
137 if (maxlv[j] > vi) maxlv[j] = vi;
138 if (maxlv[j] < minlv[j])
139 {
140 flag = false;
141 break;
142 }
143 }
144 }
145 }
146 if (!flag) printf("-1\n");
147 else
148 {
149 init(2 * n + 2, 0, 2 * n + 1);
150 for (int i = 1; i <= n; i++)
151 {
152 addEdge(0, i, 1, 0);
153 }
154 for (int i = 1; i <= n; i++)
155 {
156 for (int j = minlv[i]; j <= maxlv[i]; j++)
157 {
158 addEdge(i, n + j, 1, 0);
159 }
160 }
161 for (int i = n + 1; i <= 2 * n; i++)
162 {
163 for (int j = 1; j <= n; j++)
164 {
165 addEdge(i, 2 * n + 1, 1, j*j - (j - 1)*(j - 1));
166 }
167 }
168 int totflow = 0, totcost = 0;
169 MCMF(source, sink, totcost, totflow);
170 //if (totcost < n) printf("-1\n");
171 //else printf("%d\n", totcost);//之前flag判断是否可行也可用该步来替换
172 printf("%d\n", totcost);
173 }
174 return 0;
175 }
View Code