2013ACM省赛题目

地址就贴这一个吧都在附近

当时回来也没做做一伤心了二是当时实在太弱了

先补两道DP

E题的区间DP

dp[i][j] 截止到i位置以字母j为结束的上升序列正序逆序各来一遍再循环一遍保存一下小于等于J结束的有多少

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define LL long long

 #define N 100010

 #define mod 2012

 LL dp1[N][];

 LL dp2[N][];

 char s[N];

 int main()

 {

     int i,j,k,n;

     while(scanf("%d",&n)!=EOF)

     {

         scanf("%s",s);

         memset(dp1,,sizeof(dp1));

         memset(dp2,,sizeof(dp2));

         for(i =  ; i <= n ; i++)

         {

             k = s[i-]-'a';

             dp1[i][k] = ;

             for(j =  ;j < k ; j++)

             dp1[i][k]=(dp1[i][k]+dp1[i-][j])%mod;

             for(j =  ; j <  ; j++)

             dp1[i][j] = (dp1[i-][j]+dp1[i][j])%mod;

         }

         for(i =  ; i <= n ; i++)

         {

             for(j =  ; j <  ; j++)

             dp1[i][j] = (dp1[i][j]+dp1[i][j-])%mod;

         }

         for(i = n ; i>=  ; i--)

         {

             k = s[i-]-'a';

             dp2[i][k] = ;

             for(j =  ; j < k ; j++)

             dp2[i][k] = (dp2[i+][j]+dp2[i][k])%mod;

             for(j =  ; j <  ; j++)

             dp2[i][j] = (dp2[i+][j]+dp2[i][j])%mod;

         }

         for(i = n ; i >= ; i--)

            for(j =  ; j <  ; j++)

            dp2[i][j] = (dp2[i][j]+dp2[i][j-])%mod;

         int ans = ;

         for(i = ; i < n ; i++)

         {

             k = s[i-]-'a';

             if(k!=)

             ans = (ans+dp1[i-][k-]*dp2[i+][k-])%mod;

         }

         printf("%d\n",ans);

     }

     return ;

 }

I 题概率DP

虽然对概率题并不是很了解不过这题真心不难我是以比较挫的方法过的时间卡得还不算多紧过完发现就我500多ms 人家都是0ms过的。。

发现好像直接乘就可以了不用管步数。。概率有待加强。。贴我的三维的

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 double dp[][][];

 int main()

 {

     int i,j,g,n;

     while(scanf("%d",&n)!=EOF)

     {

         if(!n) break;

         memset(dp,,sizeof(dp));

         double a,b,c,d,e;

         double aa,bb,cc;

         scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);

         dp[][][] = ;

         for(i = ; i <= n ; i++)

             for(j = i; j >=  ; j--)

             {

                 if(i==n) aa = ;

                 else aa = e;

                 if(j==) cc = a;

                 else cc = c;

                 if(j==) bb = b;

                 else bb = d;

                 for(g =  ; g <= *(i+) ; g++)

                 {

                     dp[i][j][g] = dp[i][j+][g-]*aa+dp[i-][j-][g-]*bb+dp[i-][j][g-]*cc;

                 }

             }

         double ans=;

         for(i = ; i <= *(n+) ; i++)

         {

             ans+=dp[n][][i]*i;

         }

         printf("%.2lf\n",ans);

     }

     return ;

 }

B题 BFS

 #include <iostream>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<cstdio>

 #include<queue>

 using namespace std;

 struct node

 {

     int u,v,next;

 }ed[];

 int w[][];

 int head[],vis[],t,n,m;

 void init()

 {

     t=  ;

     memset(head,-,sizeof(head));

     memset(w,,sizeof(w));

 }

 void add(int u,int v)

 {

     ed[t].u = u;

     ed[t].v = v;

     ed[t].next = head[u];

     head[u] = t++;

 }

 void spfa(int u,int st)

 {

     memset(vis,,sizeof(vis));

     queue<int>q;

     q.push(u);

     vis[u] = ;

     while(!q.empty())

     {

         int tu = q.front();

         q.pop();

         w[u][tu] = ;

         w[tu][u] = ;

         for(int i = head[tu] ; i != -; i = ed[i].next)

         {

             int tv = ed[i].v;

             if(!vis[tv])

             {

                 vis[tv] = ;

                 q.push(tv);

             }

         }

     }

 }

 int main()

 {

     int i,j,k,kk=;

     scanf("%d",&k);

     while(k--)

     {

         init();

         kk++;

         scanf("%d%d",&n,&m);

         for(i = ; i <= m ; i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             add(u,v);

         }

         int f = ;

         for(i = ; i <= n ;i++)

         {

             for(j = ; j <= n ; j++)

             {

                 if(!w[i][j])

                 {

                     spfa(i,j);

                     if(!w[i][j])

                     spfa(j,i);

                 }

                 if(!w[i][j])

                 {

                     f = ;

                     break;

                 }

             }

             if(!f) break;

         }

         printf("Case %d: ",kk);

         if(f)

         {

             puts("Kalimdor is just ahead");

         }

         else

         puts("The Burning Shadow consume us all");

     }

     return ;

 }

 /**************************************

     Problem id    : SDUT OJ 2604

     User name    : shang

     Result        : Accepted

     Take Memory    : 16412K

     Take Time    : 380MS

     Submit Time    : 2013-09-18 11:59:41

 **************************************/

H 题线段树离线处理

有点小技巧区间 l,r,s,e

将元素按从小到大排序区间按e排序依次插入询问求和再按s排序求差

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define N 50010

 #define lowbit(x) (x&(-x))

 #define pp 100000010

 #define LL long long

 int re[N<<];

 struct node

 {

     int l,r,id;

     LL s,e;

 }p[N];

 int ans[N][];

 struct mode

 {

     int id;

     LL a;

 }q[N];

 int s[N<<];

 bool cmp(mode a,mode b)

 {

     return a.a<b.a;

 }

 bool cmpp(node a,node b)

 {

     return a.e<b.e;

 }

 bool cmppp(node a,node b)

 {

     return a.s<b.s;

 }

 void up(int l,int r,int w)

 {

     s[w] = s[w<<]+s[w<<|];

 }

 void update(int p,int l,int r,int w)

 {

     if(l==r)

     {

         s[w] = ;

         return ;

     }

     int m = (l+r)>>;

     if(p<=m)

     update(p,l,m,w<<);

     else

     update(p,m+,r,w<<|);

     up(l,r,w);

 }

 int query(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         return s[w];

     }

     int m = (l+r)>>,re=;

     if(a<=m)

     re+=query(a,b,l,m,w<<);

     if(b>m)

     re+=query(a,b,m+,r,w<<|);

     return re;

 }

 int main()

 {

     int t,i,n,m,kk=;

     scanf("%d",&t);

     while(t--)

     {

         memset(s,,sizeof(s));

         scanf("%d%d",&n,&m);

         kk++;

         for(i = ; i <= n ; i++)

         {

             scanf("%lld",&q[i].a);

             q[i].id = i;

         }

         sort(q+,q+n+,cmp);

         for(i = ; i <= m ; i++)

         {

             scanf("%d%d%lld%lld",&p[i].l,&p[i].r,&p[i].s,&p[i].e);

             p[i].id = i;

         }

         sort(p+,p+m+,cmpp);

         int o = ;

         for(i =; i <= m ; i++)

         {

             while(o<=n&&q[o].a<=p[i].e)

             {

                 update(q[o].id,,n,);

                 o++;

             }

             ans[p[i].id][] = query(p[i].l,p[i].r,,n,);

         }

         memset(s,,sizeof(s));

         sort(p+,p+m+,cmppp);

         o = ;

         for(i = ; i <= m ; i++)

         {

             while(o<=n&&q[o].a<p[i].s)

             {

                 update(q[o].id,,n,);

                 o++;

             }

             ans[p[i].id][] = query(p[i].l,p[i].r,,n,);

         }

         printf("Case #%d:\n",kk);

         for(i = ; i <= m ; i++)

         printf("%d\n",ans[i][]-ans[i][]);

     }

     return ;

 }

 /**************************************

     Problem id    : SDUT OJ 2610

     User name    : shang

     Result        : Accepted

     Take Memory    : 4004K

     Take Time    : 400MS

     Submit Time    : 2013-09-19 14:37:01

 **************************************/

巴特西

2013ACM省赛题目

最新文章

热门文章