2016″百度之星” – 复赛(Astar
Round3)

1、Quasi-palindrome

1003 拍照

思路:先把所有的线条在x轴上可观察到的地方求出来,起源和顶峰对应数组a里的x,y,排序后从坐标最小开端枚举。即使赶上源点标志,就加一(表明从那个职位上马可先生以望见);截至点注脚减一(表明从那几个岗位上马不可知)。还有一个值得注意的是:唯有向左行驶的船舶可知坐标大于向右行驶的船只,才可能在某个时刻同时出现在照片里

图片 1图片 2

/**************************************************************
    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)

1001 区间的市值

思路:先选出[l,r]距离内的矮小值,然后枚举[l,r]内的所以值,就足以算出以a[p]为最小值的富有区间的【区间的价值】了;不过有少数需求小心:在以a[p]为
       
 最小值时,统计出的【区间大小大于等于3】(要是间隔大小为k)的【区间的价值】,应该是距离大小为[2,k]内的最大值。

图片 3图片 4

/**************************************************************
    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

 1003 瞬间运动

思路:C(n-2,n+m-4);

1005 区间交

思路:对区间起末坐标存入数组排序,然后枚举,蒙受源点存入队列,碰到末点更新答案。下边是具体做法:

用y数组记录下各类区间的id,l,r;并用x数组记录下区间的id,区间起(末)坐标并标记为起(末);对x数组举办排序,然后一一枚举x数组并将符号为先导点的坐标压入队列,那里的队列用数组完毕。当然这一个历程大家必要多个数组:index用来标记队列中点对应的间距id,pt用来标记区间id对应队列中的地方。如若为起头点,那么大家直接压入队列就好了。若是为末点,大家就得处理他。

拍卖操作:

  1. 第一,倘若队列元素个数小于k,直接把队列中id对应的职分弹出去就好了,大家那里是符号为-1;
  2. 假若个数大于等于k,大家就创新答案。因为我们早已对x排序过,所以先进行列的开局坐标值肯定更小;而我辈只需求k个区间交就可以了,所以大家取队列中的第k个值来测算。那里第k个值所对应队列中的地方我们用flag记录。
  3. 若是当前处理的id在队列中的位置在flag后边,那么flag指向的是k-1个区间交的地方,所以我们要不停向后搜索。因为被弹骑行列的岗位都被标记为-1,所以while循环到非-1就是眼下的k个区间交对应的职位。

图片 5图片 6

/**************************************************************
    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

 

1006 中位数计数

思路:那个题材可分类为01分数规划里总括果了,所以已经链接到那篇博文了

 

2016″百度之星” – 初赛(Astar
Round2A)

1001 ALL X

思路:x*(10n-1)/9,之后的应当就大致了

1002  Sitting in Line

其一已经再博客里写过了,所以把标题已经连续到写的丰盛博客了

1003 snacks

思路:那些题要求一个子树里的最大值。先dfs三次整棵树,并且记下一个点进去时候的id和出去的id,那么这八个id之间就是那几个点的子树了。然后利用线段树处理一下,nlogn复杂度

图片 7图片 8

/**************************************************************
    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的地点重复统计了一遍,所以要去掉这一片段

图片 9图片 10

/**************************************************************
    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’都去掉,然后看其是不是为回文串

图片 11图片 12

 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辆单人车,问每辆双人车上五个人的体重之差的和微小是有点

  思路:先把体重从小到大排序,然后枚举不坐双人车的多少人,算出剩下的人的小小体重差的和,取最小值。

图片 13图片 14

 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和鲍伯的得分

  思路:找到循环节。

图片 15图片 16

  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是将某个区间内的数反转。给出初阶数组和若干操作后,问若干下标地点的数是什么人

  思路:对每一个所精晓的底下的数,从最终三回操作向前找其相应的起初数组的下标。

图片 17图片 18

 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

  题意:有好三个区间,现在亟待确定是还是不是有结余的区间,使得在去掉这一个区间后本来至少被一个间隔覆盖的总长度不会回落。若存在,输出任意一个满足条件的间距的数码。

  思路:把区间按左端点排序,假如当前距离的右端点小于等于当前的最右端,则该距离就是剩下区间;否则,假如当前距离的左端点比当下最右端还要大,则更新当前距离最左端和眼前距离最右端;否则,假使当前距离的下一个间隔和当下最左端和最右端构成的间距可以覆盖当前距离,则当前距离就是剩下区间。

图片 19图片 20

 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,即标题所要求的)

图片 21图片 22

  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

 

相关文章