==========早上========http://bailian.openjudge.cn/oitraining2016c/

听说B题有毒

拿到题

F题中文题

看了一下,感觉sb题,过了

dfs大法好

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long dp[25][25][25];
long long dfs(int x,int y,int z)
{
    if (y<0) return 0;
    if (x<0) return 0;
    if (y==0) return 1;
    if (dp[x][y][z]!=-1) return dp[x][y][z];
    int i;
    long long ans=0;
    for (i=0;i<=z;i++)
    {
        ans+=dfs(x-1,y-i,i);
    }
    dp[x][y][z]=ans;
    return ans;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int i;
    memset(dp,-1,sizeof(dp));
    for (i=0;i<t;i++)
    {
        int x,y;
        scanf("%d%d",&y,&x);
        int j;
        cout<<dfs(x,y,y)<<endl;
    }
    return 0;
}

然后看有人过了C就做了C

做一回跟榜选手吧

数学题,我不会

不过...

*题意:s个珠子选c个颜色不计顺序的排成一个环,求有多少种排法

s=2,c=5的样例:

sc<=32

你sc<=32我虚个鬼啊暴力上

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int ans[10005];
int n;
int anses=0;
void dfs(int x,int y)
{
    if (x==0)
    {
        int i;
        for (i=0;i<n;i++)
        {
            ans[i+n]=ans[i];
        }
        for (i=1;i<n;i++)
        {
            int j;
            for (j=0;j<n;j++)
            {
                if (ans[j]>ans[i+j]) return;
                if (ans[j]<ans[i+j]) break;
            }
        }
        anses++;
        for (i=0;i<n+n;i++)
        {
            int j;
            for (j=0;j<n;j++)
            {
                if (ans[(i-j+n+n)%n]!=ans[j]) break;
            }
            if (j==n)
            {
                anses++;
                return;
            }
        }
        return;
    }
    int i;
    for (i=0;i<y;i++)
    {
        ans[x-1]=i;
        dfs(x-1,y);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        int x,y;
        scanf("%d%d",&y,&x);
        if ((y==0)&&(x==0)) return 0;
        n=x;
        anses=0;
        dfs(x,y);
        printf("%d\n",anses/2);
    }
    return 0;
}

然后..

看着榜,大家都做了B

思考了下不会

接着跟着过的人少的做

D题题意:

求一个点到所有其他点的距离之和最小

注意只能在点上不能在边上..最后结果乘以[tex]I^2R[/tex]

I和R都是定值..所以说白了就是求一遍每个点为中心别的点到这个点的距离之和

..树链剖分的dfs1即可吧..

感觉瞬间成水题了..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long lost_child[50005];
long long lost_father[50005];
int father[50005];
int size[50005];
struct edge
{
    int y;
    edge * next;
};
edge * li[50005];
int top=0;
edge * new_edge()
{
    static edge a[100005];
    return &a[top++];
}
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
void dfs1(int x)
{
    edge * t;
    size[x]=1;
    lost_child[x]=0;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        father[t->y]=x;
        dfs1(t->y);
        size[x]+=size[t->y];
        lost_child[x]+=size[t->y];
        lost_child[x]+=lost_child[t->y];
    }
}
void dfs2(int x,int up)
{
    lost_father[x]=up;
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        dfs2(t->y,up+size[0]+lost_child[x]-lost_child[t->y]-size[t->y]-size[t->y]);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int n;
        scanf("%d",&n);
        int i,r;
        scanf("%d%d",&i,&r);
        int ans=i*i*r;
        top=0;
        memset(li,0,sizeof(li));
        for (i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            insert_edge(x,y);
        }
        dfs1(0);
        dfs2(0,0);
        long long min_ans=9999999999999999ll;
        for (i=0;i<n;i++)
        {
            min_ans=min(min_ans,lost_child[i]+lost_father[i]);
        }
        cout<<min_ans*ans<<'\n';
        int flag=0;
        for (i=0;i<n;i++)
        {
            if (lost_child[i]+lost_father[i]==min_ans)
            {
                if (flag==0) flag=1; else printf(" ");
                printf("%d",i+1);
            }
        }
        printf("\n");
        cout<<endl;
    }
    return 0;
}

然后看E

求怎么才能使得任意两点有完全不相交的两条路径连接..

一个强联通分量,然后每次求最远的两个点连起来..

是某安徽的人火车上教我的算法..很果断的用上AC了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    edge * next;
    edge * anti;
};
edge * li[100005];
int top=0;
edge * new_edge()
{
    static edge a[100005];
    return &a[top++];
}
edge * inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
    return t;
}
void insert_edge(int x,int y)
{
    edge * t1=inserts(x,y);
    edge * t2=inserts(y,x);
    t1->anti=t2;
    t2->anti=t1;
}
int dfn[100005],low[100005];
int belong_to[100005];
int size[100005];
int newn;
void scc(int x)
{
    static int que[100005];
    static int rail=0;
    que[rail++]=x;
    static int id=0;
    dfn[x]=id++;
    low[x]=dfn[x];
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==-1) continue;
        if (dfn[t->y]==-1)
        {
            t->anti->y=-1;
            scc(t->y);
            t->anti->y=x;
            low[x]=min(low[x],low[t->y]);
        }
        else
        {
            low[x]=min(low[x],dfn[t->y]);
        }
    }
    if (low[x]==dfn[x])
    {
        newn++;
        for (;;)
        {
            rail--;
            belong_to[que[rail]]=newn;
            size[x]++;
            if (que[rail]==x) return;
        }
    }
}
int x[100005],y[100005];
int dist[100005];
void dfs(int x)
{
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==-1) continue;
        t->anti->y=-1;
        dist[t->y]=dist[x]+1;
        dfs(t->y);
        t->anti->y=x;
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        x[i]--;
        y[i]--;
        insert_edge(x[i],y[i]);
    }
    int sum=0;
    for (;;)
    {
        memset(dfn,-1,sizeof(dfn));
        newn=-1;
        scc(0);
        if (newn==0)
        {
            printf("%d\n",sum);
            return 0;
        }
        memset(li,0,sizeof(li));
        top=0;
        for (i=0;i<m;i++)
        {
            x[i]=belong_to[x[i]];
            y[i]=belong_to[y[i]];
            if (x[i]==y[i]) continue;
            insert_edge(x[i],y[i]);
        }
        dist[0]=0;
        dfs(0);
        int i;
        int max_dist=0;
        for (i=0;i<=newn;i++)
        {
            if (dist[i]>max_dist) max_dist=dist[i];
        }
        int val1=0;
        for (i=0;i<=newn;i++)
        {
            if (dist[i]==max_dist)
            {
                val1=i;
                dist[i]=0;
                dfs(i);
                break;
            }
        }
        for (i=0;i<=newn;i++)
        {
            if (dist[i]>max_dist) max_dist=dist[i];
        }
        for (i=0;i<=newn;i++)
        {
            if (dist[i]==max_dist)
            {
                insert_edge(val1,i);
                break;
            }
        }
        sum++;
    }
    return 0;
}

最后看A

*题意:给你个消灭星星的地图,只有三个颜色,你需要按照他的要求把星星消灭掉..

是个消灭星星类似的题,不过只有三个颜色

写了个暴力..TLE

仔细看题..

我擦?选最大的?然后优先最左?再优先最下?

然后发现自己把消两个的情况给弄爆掉了..又手动加了一个

过了..

额..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[10][16];
int max_score=0;
int now_ans=0;
int size;
void dfses(int x,int y,bool vis[10][15])
{
    if (vis[x][y]) return;
    vis[x][y]=true;
    size++;
    if ((x>0)&&(a[x-1][y]==a[x][y])) dfses(x-1,y,vis);
    if ((y>0)&&(a[x][y-1]==a[x][y])) dfses(x,y-1,vis);
    if ((x<9)&&(a[x+1][y]==a[x][y])) dfses(x+1,y,vis);
    if ((y<14)&&(a[x][y+1]==a[x][y])) dfses(x,y+1,vis);
}
void clear(int x,int y)
{
    static bool clears[10][15];
    memset(clears,0,sizeof(clears));
    size=0;
    dfses(x,y,clears);
    int i;
    for (i=0;i<10;i++)
    {
        int j;
        for (j=0;j<15;j++)
        {
            if (clears[i][j]) a[i][j]='\0';
        }
    }
    int j;
    int sum[15];
    for (j=0;j<15;j++)
    {
        sum[j]=0;
    }
    for (i=9;i>=0;i--)
    {
        int j;
        for (j=0;j<15;j++)
        {
            if (a[i][j]=='\0')
            {
                sum[j]++;
            }
            else
            {
                if (sum[j]==0) continue;
                a[i+sum[j]][j]=a[i][j];
                a[i][j]='\0';
            }
        }
    }
    int left=0;
    for (j=0;j<15;j++)
    {
        if (sum[j]==10)
        {
            left++;
        }
        else
        {
            for (i=0;i<10;i++)
            {
                if (left==0) continue;
                a[i][j-left]=a[i][j];
                a[i][j]='\0';
            }
        }
    }
}
int oper_list[105];
int best_oper_list[105];
int opers=0;
void dfs(int num)
{
    int i;
    char temp[10][15];
    int r=0,g=0,b=0;
    for (i=0;i<10;i++)
    {
        int j;
        for (j=0;j<15;j++)
        {
            if (a[i][j]=='R') r++;
            if (a[i][j]=='G') g++;
            if (a[i][j]=='B') b++;
            temp[i][j]=a[i][j];
        }
    }
    if ((r==0)&&(g==0)&&(b==0)) now_ans+=1000;
    if (now_ans>=max_score)
    {
        opers=num;
        max_score=now_ans;
        memcpy(best_oper_list,oper_list,sizeof(oper_list));
    }
    if ((r==0)&&(g==0)&&(b==0))
    {
        now_ans-=1000;
        return;
    }
    bool vis[10][15];
    memset(vis,0,sizeof(vis));
    int max_ans=0;
    for (i=0;i<10;i++)
    {
        int j;
        for (j=0;j<15;j++)
        {
            if (a[i][j]=='\0') continue;
            if (vis[i][j]) continue;
            size=0;
            dfses(i,j,vis);
            max_ans=max(max_ans,size);
        }
    }
    if (max_ans==1) return;
    memset(vis,0,sizeof(vis));
    int j;
    for (j=0;j<15;j++)
    {
        for (i=9;i>=0;i--)
        {
            if (a[i][j]=='\0') continue;
            if (vis[i][j]) continue;
            size=0;
            dfses(i,j,vis);
            if (size==1) continue;
            if (size!=max_ans) continue;
            int t_size=size;
            now_ans+=(size-2)*(size-2);
            clear(i,j);
            oper_list[num]=i*15+j;
            dfs(num+1);
            now_ans-=(t_size-2)*(t_size-2);
            int i;
            for (i=0;i<10;i++)
            {
                int j;
                for (j=0;j<15;j++)
                {
                    a[i][j]=temp[i][j];
                }
            }
            return;
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    int flag=0;
    for (zu=0;zu<t;zu++)
    {
        if (flag==0) flag=1; else printf("\n");
        printf("Game %d:\n\n",zu+1);
        int i;
        max_score=0;
        opers=0;
        for (i=0;i<10;i++)
        {
            scanf("%s",a[i]);
        }
        dfs(0);
        for (i=0;i<opers;i++)
        {
            int x=best_oper_list[i]/15;
            int y=best_oper_list[i]%15;
            char col=a[x][y];
            printf("Move %d at (%d,%d):",i+1,10-x,1+y);
            clear(x,y);
            printf(" removed %d balls of color %c, got %d points. \n",size,col,(size-2)*(size-2));
        }
        int cnt=0;
        for (i=0;i<10;i++)
        {
            int j;
            for (j=0;j<15;j++)
            {
                if (a[i][j]!='\0') cnt++;
            }
        }
        printf("Final score: %d, with %d balls remaining.\n",max_score,cnt);
    }
    return 0;
}

过了A没时间了

5题

======下午=======http://bailian.openjudge.cn/oitraining2016d/

下午拿到题

看到中文题秒了..暴力模拟..

A题不是一血....

额..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<memory>
#include<math.h>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<fstream>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[15],b[15],c[15];
int ans[15];
int n,m;
int k;
bool check(int x)
{
    int i;
    for (i=0;i<n;i++)
    {
        if (a[i]>=x+'0') return false;
    }
    for (i=0;i<m;i++)
    {
        if (b[i]>=x+'0') return false;
    }
    for (i=0;i<15;i++)
    {
        ans[i]=0;
    }
    for (i=0;a[i]!='\0';i++)
    {
        int j;
        for (j=0;b[j]!='\0';j++)
        {
            ans[n+m-i-j-2]+=(a[i]-'0')*(b[j]-'0');
        }
    }
    for (i=0;i<=n+m;i++)
    {
        ans[i+1]+=ans[i]/x;
        ans[i]%=x;
        if ((ans[i]==0)&&(k-i-1<0)) continue;
        if (ans[i]!=c[k-i-1]-'0') return false;
    }
    return true;
}
int main()
{
    scanf("%s%s%s",a,b,c);
    n=strlen(a);
    m=strlen(b);
    k=strlen(c);
    int i;
    for (i=2;i<=1000;i++)
    {
        if (check(i))
        {
            printf("%d\n",i);
            return 0;
        }
    }
    printf("0\n");
    return 0;
}

然后看别的题

B题似乎是有毒的题..虽然是中文题

看看榜,E题一个kmp+dp一样的东西..

强行写成AC自动机的形式,过掉了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<memory>
#include<math.h>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<fstream>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int fail[1005];
int child[1005][30];
char a[1005];
double cent[45];
double percent[1005];
double next_percent[1005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if ((n==0)&&(m==0)) return 0;
        int i;
        for (i=0;i<26;i++)
        {
            cent[i]=0;
        }
        for (i=0;i<n;i++)
        {
            double x;
            scanf("%s%lf",a,&x);
            cent[a[0]-'a']=x;
        }
        scanf("%s",a);
        n=strlen(a);
        a[n]='z'+1;
        fail[1]=-1;
        for (i=0;i<26;i++)
        {
            child[0][i]=0;
        }
        for (i=0;i<n;i++)
        {
            child[i][a[i]-'a']=i+1;
            int j;
            fail[i+1]=child[fail[i]][a[i]-'a'];
            if (i==0) fail[i+1]=0;
            for (j=0;j<26;j++)
            {
                child[i+1][j]=child[fail[i+1]][j];
            }
        }
        memset(next_percent,0,sizeof(next_percent));
        next_percent[0]=1;
        for (i=0;i<m;i++)
        {
            int j;
            for (j=0;j<n;j++)
            {
                percent[j]=next_percent[j];
                next_percent[j]=0;
            }
            for (j=0;j<n;j++)
            {
                int i;
                for (i=0;i<26;i++)
                {
                    //cent[i] to write i+'a'
                    next_percent[child[j][i]]+=percent[j]*cent[i];
                }
            }
        }
        printf("%.2lf%%\n",next_percent[n]*100);
    }
}

然后决定抢个一血

C题题目似乎有点问题是55不是57.

C题题意:2个人取石头,n个石头

第一个人第一步可以取[1,n-1]个,之后如果对手取了x个你最多可以取kx个

如果你(先手)必败输出lose,不然输出第一次取几个

打了个表找了个规律

对于在k的情况下

我们定义,n=1视为不可行,必败

如果x是不可行的,当且仅当对于最大的不可行的y<x,使得x-y也是不可行的并且(x-y)*k>=y(也就是如果取x-y个会被对手一次取完)

如果x是可行的,则x=x-y,递归下去,输出递归到的第一个不可行的数字

然后..过了

一血

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<memory>
#include<math.h>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<fstream>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[1000005];
int now;
void make_k(int k)
{
    int i;
    a[0]=1;
    now=1;
    int last=1;
    i=0;
    for (;;)
    {
        if (last+a[i]<=(long long)(k+1)*a[i])
        {
            a[now++]=last+a[i];
            //printf("%d ",a[now-1]);
            last+=a[i];
        }
        else
        {
            i++;
        }
        if (last>=100000000) return;
    }
}
void dfs(int n,int flag=0)
{
    int t=lower_bound(a,a+now,n)-a;
    if (a[t]==n)
    {
        if (flag==0)
        {
            printf("lose\n");
        }
        else
        {
            printf("%d\n",a[t]);
        }
        return;
    }
    t--;
    dfs(n-a[t],1);
}
int main()
{
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        printf("Case %d: ",zu+1);
        int n,k;
        scanf("%d%d",&n,&k);
        if ((n==0)&&(k==0)) return 0;
        make_k(k);
        dfs(n);
    }
    return 0;
}
/*
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<memory>
#include<math.h>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<fstream>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
bool ok[10005][3005];
int main()
{
    freopen("biao.txt","w",stdout);
    int k;
    scanf("%d",&k);
    int i;
    memset(ok[0],false,sizeof(ok[0]));
    for (i=2;i<=100;i++)
    {
        int j;
        bool checked=false;
        printf("%d :",i);
        for (j=k;j<=i;j+=k)
        {
            int l;
            for (l=1;l<=j;l++)
            {
                if ((ok[i-l][k*l]==false)&&(k*l<i-l))
                {
                    ok[i][j]=true;
                    if (!checked) printf("%d ",l);
                    checked=true;
                }
            }
        }
        if (!checked) printf("lose");
        printf("\n");
    }
}
*/

底下是打表程序啦~

感觉今天的1A率明显提高,虽然每场都是5题但罚时都不算太多

然后再开F题

*题意:n个点m条边的图,求1到每个点距离之和+每个点到1的距离之和

两次dijkstra的逗比题..秒了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<memory>
#include<math.h>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<fstream>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int top=0;
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * li[1000005];
edge * li2[1000005];
edge * new_edge()
{
    static edge a[2000005];
    return &a[top++];
}
void inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
void inserts_anti(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li2[x];
    li2[x]=t;
}
void insert_edge(int x,int y,int z)
{
    inserts(x,y,z);
    inserts_anti(y,x,z);
}
long long dist[1000005];
bool visit[1000005];
void dijkstra()
{
    memset(dist,-1,sizeof(dist));
    memset(visit,false,sizeof(visit));
    priority_queue<pair<long long,int> > q;
    q.push(make_pair(0ll,0));
    dist[0]=0;
    for (;!q.empty();)
    {
        edge * t;
        int now=q.top().second;
        q.pop();
        if (visit[now]) continue;
        visit[now]=true;
        for (t=li[now];t!=0;t=t->next)
        {
            if ((dist[t->y]==-1)||(dist[t->y]>dist[now]+t->weight))
            {
                dist[t->y]=dist[now]+t->weight;
                q.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
}
void dijkstra_anti()
{
    memset(dist,-1,sizeof(dist));
    memset(visit,false,sizeof(visit));
    priority_queue<pair<long long,int> > q;
    q.push(make_pair(0ll,0));
    dist[0]=0;
    for (;!q.empty();)
    {
        edge * t;
        int now=q.top().second;
        q.pop();
        if (visit[now]) continue;
        visit[now]=true;
        for (t=li2[now];t!=0;t=t->next)
        {
            if ((dist[t->y]==-1)||(dist[t->y]>dist[now]+t->weight))
            {
                dist[t->y]=dist[now]+t->weight;
                q.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        top=0;
        memset(li,0,sizeof(li));
        memset(li2,0,sizeof(li2));
        int n,m;
        scanf("%d%d",&n,&m);
        int i;
        for (i=0;i<m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            x--;
            y--;
            insert_edge(x,y,z);
        }
        dijkstra();
        long long ans=0;
        for (i=0;i<n;i++)
        {
            ans+=dist[i];
        }
        dijkstra_anti();
        for (i=0;i<n;i++)
        {
            ans+=dist[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

开开D题

*题意:每个点要么自身有灯并且灯开了,要么被横竖同时照到,称之为"照赵亮的"

希望你求一个最小的亮度,使得每个点都被赵亮,每个灯有个最大亮度,如果超过了它视为这个灯被关上了

每个灯的赵亮范围如下(如图是亮度为3的赵亮范围)

这题似乎有难度..

我们可以把横竖分开考虑,不要理会奇怪的数据范围..

每次考虑一横行或者一竖列,我们思考

这一横行有n个灯,那么我们给他们按照亮度排序,然后按照亮度逐个关掉

每个灯被关了以后,计算它左右开着的灯的距离以计算出关了这个灯以后所需要的最小亮度范围

把这个区间打成false(注意如果在这个范围有别的灯爆炸了在那个灯爆了的时候还会接着打tag)

复杂度O(nm log)过的是稳的..

然后就写了个O(nm log)

结果..因为作死写了个multiset,很果断的TLE了..

后来发现multiset是不必要的

所以删了,过了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<memory>
#include<math.h>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<fstream>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[105][10005];
int b[10005];
int ans[10005];
int flag[10005];
int n,m;
struct node
{
    int val;
    int id;
    inline friend bool operator < (const node &a,const node &b)
    {
        return a.val<b.val;
    }
};
struct lists
{
    int val;
    lists * pre;
    lists * next;
};
lists * li[10005];
lists aa[10005];
node c[10005];
inline int dist(int x,int y,int k)
{
    if ((x==k)&&(y==-1)) return 100000;
    if (x==k) return x-y;
    if (y==-1) return x+1;
    return (x-y)/2+1;
}
void check_ans(int k)
{
    int i;
    lists * start=&aa[k];
    start->next=&aa[0];
    start->val=-1;
    lists * end=&aa[k+1];
    end->pre=&aa[k-1];
    end->val=k;
    for (i=0;i<k;i++)
    {
        c[i].val=b[i];
        c[i].id=i;
        aa[i].val=i;
        if (i!=0) aa[i].pre=&aa[i-1]; else aa[i].pre=start;
        if (i!=k-1) aa[i].next=&aa[i+1]; else aa[i].next=end;
        li[i]=&aa[i];
        c[i].val=b[i];
        c[i].id=i;
    }
    sort(c,c+k);
    for (i=0;i<k;i++)
    {
        int t=c[i].id;
        li[t]->pre->next=li[t]->next;
        li[t]->next->pre=li[t]->pre;
        flag[c[i].val+1]=max(flag[c[i].val+1],dist(li[t]->next->val,li[t]->pre->val,k)-c[i].val-1);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        scanf("%d%d",&n,&m);
        if ((n==0)&&(m==0)) return 0;
        int i;
        for (i=1;i<=10000;i++)
        {
            ans[i]=true;
            flag[i]=0;
        }
        for (i=0;i<n;i++)
        {
            int j;
            for (j=0;j<m;j++)
            {
                scanf("%d",&a[i][j]);
                b[j]=a[i][j];
            }
            check_ans(m);
        }
        int j;
        for (j=0;j<m;j++)
        {
            int i;
            for (i=0;i<n;i++)
            {
                b[i]=a[i][j];
            }
            check_ans(n);
        }
        for (i=1;i<=10000;i++)
        {
            if (flag[i])
            {
                ans[i]=false;
                flag[i+1]=max(flag[i+1],flag[i]-1);
            }
            if (!ans[i]) continue;
            printf("%d\n",i);
            break;
        }
        if (i>=10000) printf("NO ANSWER!\n");
    }
    return 0;
}

比赛就这么结束了

昨天BC都没过,今天B都没过

B题有毒系列..

一共过了17题还算可以了..

似乎总题数全场的rank 4~5

然后..面试的结局好像和数学挺相似的..爆了

感觉好方

*B题似乎有高斯消元的倾向,不过不是很清楚..