向右看齐

题目
一句话:其实set就可以做,但是我写的是单调队列……
1A的题,不水了。
代码

#include<cstdio>
#include<cctype>
#define N 1000010
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int h[N];
struct node{
    int pos,val;
}s[N];
int ans[N],top=0;
int main(){
    freopen("lookup.in","r",stdin);
    freopen("lookup.out","w",stdout);
    int n=read();
    for(int i=1;i<=n;i++)
        h[i]=read();
    for(int i=n;i;i--){
        while(top&&h[i]>=s[top-1].val)--top;
        if(~top)ans[i]=s[top-1].pos;
        else ans[i]=0;
        s[top].val=h[i],s[top++].pos=i;
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",ans[i]);
    }
}

宴会邀请

题目
模拟题意即可
n,m看似很大,但是\sum S_i很小,模拟的删除操作总数有限。
代码

#include<cstdio>
#include<cctype>
#include<vector>
#include<set>
using std::set;
using std::vector;
#define N 100010
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int s[N];
vector<int>V[N];
set<int>S[N];
bool flag[N];
void del(int x){
    flag[x]=true;
    for(int i=0;i<V[x].size();i++){
        S[V[x][i]].erase(x);
        if(S[V[x][i]].size()==1)del(*S[V[x][i]].begin());
    }
}
int main(){
    freopen("invite.in","r",stdin);
    freopen("invite.out","w",stdout);
    int n=read(),g=read();
    for(int i=0;i<g;i++){
        s[i]=read();
        for(int j=0;j<s[i];j++){
            int t=read();
            V[t].push_back(i);
            S[i].insert(t);
        }
    }
    del(1);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(flag[i])ans++;
    }
    printf("%d\n",ans);
}

时间旅行

题目

一句话题意:

维护一个栈,有入栈弹栈操作,支持查询任意历史版本,要求每次操作后输出栈顶元素。

题解:

用链表维护,一个结点代表一个时间。
通过插入后继模拟入栈,查询前驱模拟弹栈,每一个结点下标代表时间戳,可以直接实现历史版本访问。
代码

#include<cmath>
#include<cstdio>
#include<cctype>
#define N 100010
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
struct node{
    int nxt,pre,val;
}tab[N];
int tim[N];
int n,tot=1,now=0;
int main(){
    freopen("ttravel.in","r",stdin);
    freopen("ttravel.out","w",stdout);
    n=read();
    tab[0].val=-1;
    for(int i=1;i<=n;i++){
        char str[3];
        scanf("%s",str);
        if(str[0]=='a'){
            int t=read();
            tab[now].nxt=tot;
            tab[tot].pre=now;
            tab[tot].val=t;
            now=tim[i]=tot++;
        }else if(str[0]=='s'){
            now=tab[now].pre;
            tim[i]=now;
        }else{
            now=tim[read()-1];
            tim[i]=now;
        }
        printf("%d\n",tab[now].val);
    }
}

池塘计数

题目
floodfill裸题
代码

#include<cmath>
#include<cstdio>
#include<cctype>
#define N 100010
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int n,m;
char a[110][110];
int vis[110][110];
int X[8]={1,1,1,0,0,-1,-1,-1};
int Y[8]={1,0,-1,1,-1,1,0,-1};
int tot=1;
void dfs(int x,int y,int t){
    vis[x][y]=t;
    for(int i=0;i<8;i++){
        int tx=x+X[i],ty=y+Y[i];
        if(a[tx][ty]=='W'&&vis[tx][ty]==0)dfs(tx,ty,t);
    }
}
int main(){
    freopen("lkcount.in","r",stdin);
    freopen("lkcount.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        static char str[110];
        scanf("%s",str);
        for(int j=1;j<=m;j++)a[i][j]=str[j-1];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='W'&&vis[i][j]==0){
                dfs(i,j,tot++);
            }
            //printf("%d ",vis[i][j]);
        }
        //putchar('\n');
    }
    printf("%d\n",tot-1);
}

建造道路

题目

一句话题意

给出一个图,有n个离散的点,和一些已经连好的边,任意两点间可以连边,边权为两点间欧几里得距离。现在要新连一些点,使图联通且边权和最小。要求复杂度O(n^2)

一句话题解

贪心+并查集。

一些要注意的点

100000^2在double类型下能存,但int类型下会出现负数,所以以下的语句要注意:

int a=100,b=100000;
double fault=sqrt((double)a*a+b*b);//b*b会溢出,根号下负数浮点错误
double wiser=sqrt((double)a*a+(double)b*b);//防溢出好评

代码

#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
using std::sort;
#define N 100010
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int n,m;
struct node{
    double val;
    int x,y;
    friend bool operator < (node a,node b){return a.val<b.val;}
}tab[1000010];
int tot=0;
int X[1010],Y[1010];
int fa[1010];
int find(int x){
    if(fa[x]==0)return x;
    return fa[x]=find(fa[x]);
}
bool ins(int x,int y){
    if(x==y)return false;
    int fx=find(x),fy=find(y);
    if(fx==fy)return false;
    else fa[fx]=fy;
    return true;
}
int main(){
    freopen("roads.in","r",stdin);
    freopen("roads.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        X[i]=read(),Y[i]=read();
        for(int j=1;j<i;j++){
            tab[tot].x=i,tab[tot].y=j,tab[tot++].val=sqrt((double)(X[i]-X[j])*(X[i]-X[j])+(double)(Y[i]-Y[j])*(Y[i]-Y[j]));
        }
    }
    sort(tab,tab+tot);
    double ans=0.0;
    for(int i=0;i<m;i++)ins(read(),read());
    for(int i=0;i<tot;i++){
        //printf("%lf %d %d\n",tab[i].val,tab[i].x,tab[i].y);
        if(ins(tab[i].x,tab[i].y))ans+=tab[i].val;
    }
    printf("%.2lf\n",ans);
}

接住苹果

题目

题目大意

有两棵苹果树,有 n 只苹果会从树上陆续落下。如果掉苹果的时候,贝西在那棵树下,她就能接住苹果。贝西一开始在第一棵树下。在苹果掉落之前,她有足够的时间来回走动,但她很懒,最多只愿意移动 k 次。请计算一下她最多可以接住几只苹果。

一句话题解

dp[n][k]表示第n颗苹果掉落,并且走动k次后,能接到的最多苹果数。(当然像我一样,再写一维在哪棵树下的状态也可以。不过通过k的奇偶可以O(1)判断出来就是啦)
代码

#include<cstdio>
#include<cctype>
#include<algorithm>
using std::max;
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int a[1010],sum1[1010],sum2[1010];
int dp[1010][1010][2];
int main(){
    freopen("bcatch.in","r",stdin);
    freopen("bcatch.out","w",stdout);
    int n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];
        if(a[i]==1)sum1[i]++; //dp[i][0][0]=dp[i-1][0][0]+1,dp[i][0][1]=dp[i-1][0][1];
        else sum2[i]++; //dp[i][0][1]=dp[i-1][0][1]+1,dp[i][0][0]=dp[i-1][0][0];
    }
    for(int i=1;i<=n;i++){
        dp[i][0][0]=sum1[i];
        dp[i][0][1]=sum2[i];
    }
    int ans=0;
    for(int j=1;j<=k;j++){
        for(int i=1;i<=n;i++){
            for(int k=1;k<=i;k++){
                dp[i][j][0]=max(dp[k][j-1][1]+sum1[i]-sum1[k-1],dp[i][j][0]);
                dp[i][j][1]=max(dp[k][j-1][0]+sum2[i]-sum2[k-1],dp[i][j][1]);
            }
            ans=max(ans,max(dp[n][k][0],dp[n][k][1]));
        }
    }
    printf("%d\n",ans);
}

奶牛集体照

题目
感觉是本场比赛含金量最高的一道题了

题意

有一个原序列A,和5个变化后的序列B_i,在这5个序列中,对于原序列中任意一个a_i,有且仅有一个B_i序列中相应位置的数不是a_i。现给定5B_i,求原序列A

题解

考虑任意两个数的相对位置。假设原序列中a_ia_j的前面,那么在B序列中,至多有两次a_ia_j后面。所以可以重载cmp函数,调用sort排序。

注意

编号要离散化!!!
代码

#include<cmath>
#include<cstdio>
#include<cctype>
#include<map>
#include<algorithm>
using std::make_pair;
using std::map;
using std::sort;
#define N 9997233
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int a[N],pos[N][10];
int n;
map<int,int>M;
map<int,int>::iterator r;
bool cmp(int x,int y){
    int cnt=0;
    for(int i=0;i<5;i++)if(pos[M.find(x)->second][i]<pos[M.find(y)->second][i])cnt++;
    return cnt>2;
}
int main(){
    freopen("photo.in","r",stdin);
    freopen("photo.out","w",stdout);
    n=read();
    for(int i=0;i<n;i++)
        a[i]=read(),M.insert(make_pair(a[i],1));
    int i=1;
    for(r=M.begin();r!=M.end();r++,i++)r->second=i;
        for(int i=0;i<n;i++)
            pos[M.find(a[i])->second][0]=i;
    for(int s=1;s<5;s++)
        for(int i=0;i<n;i++)
            a[i]=read(),pos[M.find(a[i])->second][s]=i;
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)printf("%d\n",a[i]);
}

奶牛抗议

题目

题意

求将一个数列分成任意组数,要求每组数在原数列上连续,且每组数的和不小于零的方案数。

题解

考虑暴力dp,dp_i表示将前i个数合法分组方案数,转移方程为

    \[dp_i=/sum_{j=0}^{i-1} dp_j*(s_i\req s_j)\]

,数组s代表前缀和,复杂度为O(n^2)
优化这个过程,因为每次都是在一个规定的s域内求dp的和,可以在一棵线段树上维护这个过程,以s为下标,dp为权值。考虑到s可正可负,值域不定,所以一定要离散化

注意

离散化!!!
代码

#include<cstdio>
#include<map>
#define lowbit(x) (x&-x)
using namespace std;
const int mod=1000000009;
int n,i,a[100010],s[100010],dp[100010],c[100010];
map<int,int>M;
map<int,int>::iterator r;
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))(c[i]+=y)%=mod;
}
int que(int x){
    int ret=0;
    for(int i=x;i;i-=lowbit(i))(ret+=c[i])%=mod;
    return ret;
}
int main(){
    freopen("protest.in","r",stdin);
    freopen("protest.out","w",stdout);
    scanf("%d",&n);
    M.insert(make_pair(0,0));
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),s[i]=s[i-1]+a[i],M.insert(make_pair(s[i],0));
    for(i=1,r=M.begin();r!=M.end();r++,i++)r->second=i;
    dp[0]=1;add(M[0],dp[0]);
    for(int i=1;i<=n;i++){
        (dp[i]+=que(M[s[i]]))%=mod;
        add(M[s[i]],dp[i]);
    }
    printf("%d\n",dp[n]);
}

"Alone is what I have. Alone protects me." -Sherlock Holmes