看心情填坑

下午打了场gym，撸文化课笔记心累就随便写一写吧。

本人能力有限，只放我做了的几道。

http://codeforces.com/gym/100812

B set of tasks

题意杀，一开始以为是要求什么距离和最小这种很傻的东西怒WA一发然后又被阳神训斥了

阳神说题意是有5000个长度5000的01串，要你找出现次数最多的一个输出，要求这个01串里1不能超过15个或小于8个并没有什么卵用直接HASH或者map乱搞应该就能过，其实bitset排序硬上O(5000/32*5000*log(5000))应该也不怂但是撸完G题还有15分钟就没写

D dream of sum

一个序列要你求最短和为0的子序列。Map或者hash链乱搞，懒得写这两个就排序了沙雕题WA3发

#include<cstdio>
#include<algorithm>
using namespace std;
long long sum;
struct ele{
    long long s;
    int k;
}e[200005];
int n,x,cnt,ans1,ans2;
inline bool cmp(ele k1,ele k2){
    if(k1.s!=k2.s)return k1.s<k2.s;
    else return k1.k<k2.k;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        sum+=x;
        e[i].k=i;
        e[i].s=sum;
    }
    sort(e,e+1+n,cmp);
    ans2=n+2;
    for(int i=1;i<=n;i++)if(e[i].s==e[i-1].s){
        if(e[i].k-e[i-1].k<ans2){
            ans1=e[i-1].k+1;
            ans2=e[i].k-e[i-1].k;
        }
    }
    if(ans2==n+2)printf("-1");
    else printf("%d %d\n",ans1,ans2);
}

E world of knights

一开始把题名看成了world of knives觉得好中二

有若干张牌，有两个属性a_i,b_i,初始你有一张属性为0,1的牌，然后你可以用手里的一张牌i来获得另外一张牌j，满足b_i>=a_j，求获得第n张牌的最小操作数（即你最少要拿几张牌来获得第n张牌）并输出方案。

一开始以为是什么单点修改然后线段树求最小值这种东西。线段树已经打好了一看，这TM不是个SB单调栈吗(╯‵□′)╯︵┻━┻。然后怒打单调栈沙雕题又怒WA一发

#include<cstdio>
#include<algorithm>
#define inf 2000000000
#define lson index<<1
#define rson index<<1
using namespace std;
int n,stack[100005],pre[100005],top,cnt;
struct ele{
    int a,b,pre,k;
}e[100005],E[100005];
bool cmp(ele k1,ele k2){
    if(k1.a!=k2.a)return k1.a<k2.a;
    else return k1.b>k2.b;
}
void print(int k,int s){
    if(k){
        print(e[k].pre,s+1);
        printf("%d ",e[k].k);
    }else printf("%d\n",s);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&E[i].a,&E[i].b),E[i].k=i;
    if(n==1){
        if(E[1].a==0)printf("1\n1");
        else printf("No such luck");
        return 0;
    }
    sort(E+1,E+n,cmp);
    cnt=1;e[1]=E[1];
    for(int i=2;i<n;i++)if((E[i].a>e[cnt].a)&&(E[i].b>e[cnt].b)){
        cnt++;
        e[cnt]=E[i];
    }
    e[0].a=0;e[0].b=1;top=1;stack[1]=0;
    for(int i=1;i<=cnt;i++){
        if(e[i].a>e[i].b)continue;
        int l=0,r=top+1;
        while(r-l>1){
            int mid=(l+r)>>1;
            if(e[stack[mid]].b>=e[i].a)r=mid;
            else l=mid;
        }
        if(r==top+1)continue;
        e[i].pre=stack[r];
        top++;
        stack[top]=i;
    }
    int l=0,r=top+1;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(e[stack[mid]].b>=E[n].a)r=mid;
        else l=mid;
    }
    if(r==top+1){
        printf("No such luck");
        return 0;
    }else{
        print(stack[r],1);
        printf("%d",n);
    }
}

F Graveyard of Bandits

题意给你一个n*m的*.矩阵，你可以在所有.的地方建墓碑，问你建1*1,1*2,1*3...1*max(n,m)的矩阵的方案数。

第一眼看n,m<=10⁵吓了一跳，发现后面还有一个n*m<=10⁶

统计出来图中所有1*1,1*2,1*3,...,1*max(n,m)的独立矩阵数（这些矩阵不能再合并成1*k），显然在一个1*i的矩阵里选一个1*j的矩阵方案是i-j+1种，前缀和乱搞搞就行，然后这样做一遍就能得到所有横着建的方案数。

然后1*1,2*1,3*1,...,max(n,m)*1竖着再搞一遍就好了，注意1*1会算两次特判掉。

#include<cstdio>
using namespace std;
int n,m;
char c[1000005];
int ans[100005];
long long A[100005];
inline int max(int x,int y){return x>y?x:y;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%s",c+i*m);
    for(int i=0;i<n;i++){
        int s=0;
        for(int j=0;j<m;j++)if(c[i*m+j]=='.')s++;
        else{
            if(s)ans[s]++;
            s=0;
        }
        if(s)ans[s]++;
    }
    for(int j=0;j<m;j++){
        int s=0;
        for(int i=0;i<n;i++)if(c[i*m+j]=='.')s++;
        else{
            if(s)ans[s]++;
            s=0;
        }
        if(s)ans[s]++;
    }
    long long Ans=0,sum=0;
    for(int i=max(n,m);i;i--){
        sum+=ans[i];
        Ans+=sum;
        if(i>1)A[i]=Ans;
        else A[i]=Ans/2;
    }
    for(int i=1;i<=max(n,m);i++)printf("%I64d ",A[i]);
}

G short path

吃完饭做的，所以没有时间打B了。

题意：给你一个20W点10W边的图，其中某些点有标记，求有标记的点之中的两点最短距离。

看边比较小感觉标算应该很巧妙，不是很会来，直接上k次SPFA，k次v全部初始化显然T，所以打了时间戳。

跑80点啥事没有很开心，然后TLE101CF卡SPFA丧心病狂

然后上读入优化还是TLE101，然后

        if(clock()>=1800){
            if(ans==1LL*n*1000000000)printf("No luck at all");
            else printf("%I64d\n%d %d",ans,x,y);
            return 0;
        }

A掉了

#include<cstdio>
#include<ctime>
using namespace std;
int f[200005],head[200005],dl[200005],B[200005];
long long v[200005];
int n,m,x,y,l,r,times,cnt;
bool b[200005];
long long ans;
struct edge{
    int next,to,l;
}e[200005];
inline long long min(long long x,long long y){return x<y?x:y;}
void add(int x,int y,int l){
    cnt++;
    e[cnt].next=head[x];
    e[cnt].to=y;
    e[cnt].l=l;
    head[x]=cnt;
}
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
void spfa(int root){
    times++;B[root]=times;
    v[root]=0;
    l=r=1;dl[1]=root;b[root]=true;
    while(true){
        if((f[dl[l]])&&(dl[l]!=root)&&(ans>v[dl[l]])){
            ans=v[dl[l]];
            x=root;
            y=dl[l];
        }
        for(int i=head[dl[l]];i;i=e[i].next)if(((B[e[i].to]<times)||(v[e[i].to]>v[dl[l]]+e[i].l))&&(v[dl[l]]+e[i].l<ans)){
            B[e[i].to]=times;
            v[e[i].to]=v[dl[l]]+e[i].l;
            if(!b[e[i].to]){
                r++;
                if(r>n)r=1;
                dl[r]=e[i].to;
                b[e[i].to]=true;
            }
        }
        b[dl[l]]=false;
        if(r==l)break;
        l++;
        if(l>n)l=1;
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)f[i]=read();
    while(m--){
        x=read();y=read();l=read();
        add(x,y,l);
        add(y,x,l);
    }
    ans=1LL*n*1000000000;
    for(int i=1;i<=n;i++)if(f[i]){
        spfa(i);
        if(clock()>=1800){
            if(ans==1LL*n*1000000000)printf("No luck at all");
            else printf("%I64d\n%d %d",ans,x,y);
            return 0;
        }
    }
    if(ans==1LL*n*1000000000)printf("No luck at all");
    else printf("%I64d\n%d %d",ans,x,y);
}

后来去看不知道是凌神还是YB的代码，这个东西好像只要BFS就行_(:зゝ∠)_果然还是我太沙雕的缘故

I Dragon Delivers

题意:给你若干个订单，每个订单可以有两种办法交付，第一种直接交付，代价为d，第二种和他之前第一个直接交付的订单合并，代价为(t_i-t_j)*c，求最小交付所有订单的方法。

dp方程很好写，dp[i]=min(dp[j]+(sum[i]-sum[j]-t[j+1]*(i-j))*c+d)感觉好像可以斜率优化。

一看数据范围，n=1k，呵呵。稍微处理一下就能去掉前缀和。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,d,c;
int x[1005];
long long dp[1005];
int main(){
    scanf("%d%d%d",&n,&d,&c);
    dp[0]=0;
    for(int i=1;i<=n;i++)scanf("%d",&x[i]);
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]+d;
        long long s=0;
        for(int j=i-1;j>=1;j--){
            s+=x[i]-x[j];
            dp[i]=min(dp[i],s*c+dp[j-1]+d);
        }
    }
    printf("%I64d\n",dp[n]);
}

J Feeling of Comradeship

初三大爷做的，我不知道。有需要的去问初三大爷一号

L Knights without Fear and Reproach

题意：有两个人一起打你，第一个人每a秒打你一下，第二个人每b秒打你一下，你假如有两秒之内被打两次就GG，问你什么时候会GG。

一眼感觉好厉害，第二眼沙雕题，只有两种可能exgcd或者lcm，别和我说你不会。

注意特判a,b里有1的情况，我没特判怒WA一发_(:зゝ∠)_

#include<cstdio>
#include<algorithm>
using namespace std;
int a,b,gcd,x,y,A,B;
long long ans;
inline int exgcd(int x, int y, int&a, int&b)  {
    if(y==0){
        a=1,b=0;  
        return x;
    }
    int g=exgcd(y,x%y,a,b);  
    int t=a;
    a=b;  
    b=t-x/y*b;  
    return g;  
}  
int main(){
    scanf("%d%d",&x,&y);
    if((x==1)&&(y==1)){
        printf("1");
        return 0;
    }
    if((x==1)||(y==1)){
        printf("2");
        return 0;
    }
    int gcd=exgcd(x,y,a,b);
    ans=1LL*x*y/gcd;
    if(gcd>1){
        printf("%I64d",ans);
        return 0;
    }
    if(a>0)ans=min(ans,1LL*a*x);
    else ans=min(ans,1LL*b*y);
    printf("%I64d\n",ans);
}

1、文化课积重难返心累啊

2、哲教阳神YB一群人看我和初三大爷在打gym就来殴打小盆友简直丧心病狂