设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

Week Part1:2014/11/2

2014-11-04 13:43:00.0 ACM_周赛  
导读:一直拖到现在才写,中间还有几道没看。。A:Aizu 0009 Prime Number:素数筛选,注意可能爆内存!!。#include#include#include#include#includetypedef long long LL;using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#...。。。

一直拖到现在才写,中间还有几道没看。。

A:Aizu 0009 Prime Number:素数筛选,注意可能爆内存!!。

#include#include#include#include#includetypedef long long LL;using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )const int N=1e7;int vis[N];void initPrime(){    int num = 0, m = sqrt (N + 0.5);    REPF(i,1,N)   vis[i]=1;    for (int i = 2; i <= m; ++i)        if (vis[i] == 1)            for (int j = i * i; j <= N; j += i) vis[j] = 0;    vis[1]=0;    for(int i=2;i<=N;i++)         vis[i]+=vis[i-1];//    for(int i=2;i<=10;i++)//        cout<<"233  "<B:Aizu 2224 Save your cat...

C:CF   250A Paper Work

题意:求最少的连续段是每段的负数个数不超过2。乱搞。

#include#include#include#include#includetypedef long long LL;using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )int a[110],n;int num[110];int main(){    while(~scanf("%d",&n))    {        REPF(i,1,n)          scanf("%d",&a[i]);        CLEAR(num,0);        int cnt=0;        int l=0;        int m=0;        REPF(i,1,n)        {            m++;            if(a[i]<0)               cnt++;            if(cnt==2)            {                cnt=0;int j;                for(j=i+1;j<=n;j++)                {                    if(a[j]<0)  break;                    else  m++;                }                num[l++]=m;                i=j-1;                m=0;            }            if(i==n&&cnt==1)  num[l++]=m;        }        if(l==0)        {            printf("%d\n%d\n",1,n);            continue;        }        printf("%d\n",l);        REP(i,l)           printf(i==l-1?"%d\n":"%d ",num[i]);    }}
D:CF 126B Password:

题意:求一个最长字串是它的前缀,后缀,和中间的一个字串相同

KMP做法:

#include #include #include #define LMT 1000005using namespace std;int hash[LMT],next[LMT],len;char str[LMT];void init(void){    int i=0,j=-1;    next[0]=-1;    while(i0)//对应aaa这种情况    {       if(hash[next[i]])       {         for(int j=0;j

F:CF 303 D Biridian Forest

题意:迷宫中到达出口,中间有人决斗,问最少的打架次数.反向BFS即可.

#include#include#include#include#includetypedef long long LL;using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )const int maxn=1100;char mp[maxn][maxn];int val[maxn][maxn];int dis[maxn][maxn];int vis[maxn][maxn];int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};int n,m,ex,ey;void BFS(){    pairst;    CLEAR(vis,0);    vis[ex][ey]=1;    dis[ex][ey]=1;    queue >q;    int dd=0x7fffff;    int num=0;    q.push(make_pair(ex,ey));    while(!q.empty())    {        st=q.front();        q.pop();        if(dis[st.first][st.second]>dd)            break;        REP(i,4)        {            int xx=st.first+dr[i][0];            int yy=st.second+dr[i][1];            if(mp[xx][yy]!='T'&&!vis[xx][yy]&&xx>=0&&xx=0&&yy='0'&&mp[i][j]<='9')                    val[i][j]=mp[i][j]-'0';            }        }        BFS();    }    return 0;}

G CF 215 D  Hot Days.

坑题,中间无限爆long long ,最后考虑极值在两端出取得。

#include#include#include#include#includetypedef long long LL;using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )const int maxn=1e5+100;LL t[maxn],T[maxn],x[maxn],cost[maxn];int n,m;LL solve(int f,LL xx){    int l=1,r=m/xx+(m%xx?1:0);    LL maxnn;    if(m<=xx)   maxnn=cost[f];    else   maxnn=cost[f]+x[f]*m;    if((LL)r*xx0)             {                LL xx=T[i]-t[i];                sum+=solve(i,xx);             }             else                sum+=((LL)m*x[i]+cost[i]);         }         printf("%I64d\n",sum);    }    return 0;}

I:HDU 1353/POJ 2581  竟然是暴力水题,我一直在在想怎么记录路径。其实开始也想到暴力,最后不敢写。POJ上必须C++交。

#include#include#include#include#includetypedef long long LL;using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )int main(){    int num1,num2,num3,num4;    int a,b,c,d;double x;    while(~scanf("%lf%d%d%d%d",&x,&num1,&num2,&num3,&num4))    {        int n=(int)(x*100);//        cout<
J:HDU 1595 find the longest of the shortest

Dijkstra求一遍记录前驱后,拆边记录最大的值。

#include#include#include#include#includetypedef long long LL;using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )const int maxn=1100;int mp[maxn][maxn];int vis[maxn],dis[maxn];int pre[maxn];int n,m;void dijkstra(int x){    int pos;    CLEAR(vis,0);    CLEAR(dis,0x3f3f3f3f);    dis[1]=0;//    vis[1]=1;    REPF(i,1,n)    {        pos=-1;        REPF(j,1,n)        {            if(!vis[j]&&(pos==-1||dis[pos]>dis[j]))                pos=j;        }        vis[pos]=1;        REPF(j,1,n)        {            if(!vis[j]&&dis[j]>dis[pos]+mp[pos][j])            {                dis[j]=dis[pos]+mp[pos][j];                if(x)     pre[j]=pos;            }        }    }}int main(){    int u,v,w;    while(~scanf("%d%d",&n,&m))    {        CLEAR(mp,0x3f3f3f);//        REPF(i,1,n)  mp[i][i]=0;        CLEAR(pre,-1);        while(m--)        {            scanf("%d%d%d",&u,&v,&w);            if(mp[u][v]>w)   mp[u][v]=mp[v][u]=w;//            cout<dd)                dd=dis[n];            mp[i][pre[i]]=mp[pre[i]][i]=t;        }        printf("%d\n",dd);    }    return 0;}


(编辑: u013582254)

网友评论
相关文章