Arab Collegiate Programming Contest 2012 解题报告(约等于AK)

比赛地址

大神都是各种ak，小菜只能赛后默默补题。。。。。。。

H题看不懂啊，，，，，，路过的帮忙一下

100多个人A的题就不说了。。。。

B题：

可以用平衡树来做，因为最多就200000个字符，所以每次可以暴力插入splay树，输出的时候也一样暴力：

#include<cstdio>#include<cstring>#define[][0]#define[][1]#define([[][1]][0])constint=200010;structSplayTree{int[];int[][2];int[];int,;inlinevoid(int){[]=1+[]+[];}inlinevoidRotate(int,int){int=[];[][!]=[][];[[][]]=;[]=[];if([])[[]][[[]][1]==]=;[][]=;[]=;();}inlinevoidSplay(int,int){//将x旋转到goal的下面while([]!=){if([[]]==)Rotate(,[[]][0]==);else{int=[],=[];int=([][0]==);if([][]==)Rotate(,!),Rotate(,);elseRotate(,),Rotate(,);}}();if(==0)=;}inlinevoid(int,int){//将第k位数旋转到goal的下面int=;while([]+1!=){if(<[]+1)=;else{-=([]+1);=;}}Splay(,);}void(int){if(){();("%c ",[]);();}}voidNewnode(int&,char,int){=++;==0;[]=;[]=1;[]=;}inlinevoid(int&,int,int,int){if(>)return;int=+>>1;Newnode(,[],);(,,-1,);(,+1,,);[]=;();}inlinevoid(int){[0][0]=[0][1]=[0]=[0]=0;==0;[0]='@';Newnode(,'@',0);Newnode([][1],'@',);[]=2;(,1,,[][1]);//vist(rt);}void(int,char)// 将c插入到第pos个元素之前{/// printf("pos=%d \n",pos);(,0);(+1,);Newnode(,,[][1]);}voidprint(int)// 输出第pos个字符{//printf("pos=%d\n",pos);(+1,0);("%c",[]);}void(){("%s",+1);int=(+1);();}void(){char[10];int,begin,end;while(("%s",)!=){if((,"END")==0)break;if([0]=='I'){("%s%d",,&);int=();for(int=0;<;++){(+1+,[]);}}else{("%d%d",&begin,&end);begin++,end++;for(int=begin;<=end;++){print();}("");}}}char[];char[];char[];};int(){.();.();return0;}

E题：

网络流，这跟上次做过的一个费用流类似，用字符个数来限定源点到每个字符的容量，然后依次去枚举每个位置所放的字符（字典序递增），用最大流判定是否有解，有解的话，立刻继续下一个位置的枚举，算是贪心吧，因为字典序就是当前字符能小则小。

#include<stdio.h>#include<string.h>constint=1010;constint=1000000000;struct{int,,next;}[1000000];int,[];int[],[];int[],[];void(int,int,int,int){/*加边的时候同时加两条，    一条正的，一条反的，    一般情况下反的容量是0 */[].=;[].=;[].next=[];[]=++;[].=;[].=;[].next=[];[]=++;}int(int,int){return(==-1||<)?:;}int(int,int,int){(,0,sizeof());(,0,sizeof());int;for(=0;<;++)[]=[];int=[]=,=0,=-1,;[0]=;while([]<){:for(=[];!=-1;=[].next){=[].;if([].>0&&[]==[]+1){=(,[].);[]=;[]=;=;if(==){for(=[];!=;=,=[]){[[]].-=;[[]^1].+=;}+=;=-1;}goto;}}int=;for(=[];!=-1;=[].next){=[].;if([].>0&&[]<){[]=;=[];}}if((--[[]])==0)break;[[]=+1]++;=[];}return;}char[110][10];bool[110][26];int[500];char[110];int;int[26];int;int,;boolReplay(){(,-1,sizeof());=0;for(int=1;<=26;++)if([-1]){//  printf("%d %d\n",S,i);(,,[-1],0);}for(int=1;<=;++){if(<=){([]-'a'+1,+26,1,0);}else{for(int=0;[][];++){([][]-'a'+1,+26,1,0);}}}for(int=1;<=;++)(+26,,1,0);return((,,+1)==);}bool(){=0;if(!Replay())returnfalse;for(int=1;<=;++){for(int=0;<26;++)if([][]){[]='a'+;=;if(Replay())break;}}returntrue;}int(){char[110];("%s",+1);=(+1);for(int=1;<=;++)[[]-'a']++;=0,=26++1;for(int=1;<=;++){("%s",[]);for(int=0;[][];++){[][[][]-'a']=true;}}if(!())("NO SOLUTION");else{for(int=1;<;++)("%c",[]);("%c\n",[]);}return0;}

G题：

水的计算几何，我还做烦 了，其实就是计算出每一条线段的张角，所有的角度加起来除以2 * pi就是答案。

F题：模拟智能手机的解锁功能， 限定一些键不能按，然后给你一个曼哈顿总距离，问你有几种不同的方案满足条件

DP吧，四维状态[x][y][len][mask]，当前的位置 ， 长度 ， 以及经过的点的集合，然后有一个很关键的地方就是当两个点的中间有点没有访问过或者有点是禁止访问的，都不能走

这题心血来潮换java写了一炮，对java 的输入输出一直有点晕，然后就先学大牛们怎么用再去理解了

import..InputStreamReader;import..IOException;import..Arrays;import..BufferedReader;import..OutputStream;import..PrintWriter;import..StringTokenizer;import..InputStream;publicclassMain{publicstaticvoid(String[]){InputStream=System.in;OutputStream=System.out;InputReaderin=newInputReader();PrintWriterout=newPrintWriter();=new();.(in,out);out.();}}class{long[][][][]=newlong[5][5][60][1<<12];int[][]=newint[10][10];int[][]=newint[10][10];int;publicvoid(InputReaderin,PrintWriterout){int,,;=in.();=in.();for(int=1;<=3;++)Arrays.([],0);for(int=0;<;++){=in.();=in.();[][]=2;}if(>55){out.("BAD MEMORY");}else{ArrayUtils.(,-1);long=0;for(int=1;<=3;++){for(int=1;<=4;++)if([][]!=2){int=(-1)*3+;[][]=(1<<(-1));}}for(int=1;<=3;++){for(int=1;<=4;++)if([][]!=2){[][]=1;+=(,,,[][]);//out.println(ans);[][]=0;//return ;}}if(!=0)out.();elseout.("BAD MEMORY");}}privatelong(int,int,int,int){if(<0)return0;if([][][][]!=-1)return[][][][];if(==0)return[][][][]=1;[][][][]=0;for(int=1;<=3;++){for(int=1;<=4;++){if(==&&==||[][]!=0)continue;boolean=true;if(Math.(-)%2==0&&Math.(-)%2==0){int=Math.(+)/2;int=Math.(+)/2;if([][]==0||[][]==2)=false;}if(==){for(int=Math.(,)+1;<=Math.(,)-1;++){if([][]==0||[][]==2)=false;}}if(!)continue;[][]=1;[][][][]+=(,,-(Math.(-)+Math.(-)),|[][]);[][]=0;}}return[][][][];}}classInputReader{BufferedReader;StringTokenizer;publicInputReader(InputStream){=newBufferedReader(newInputStreamReader());=null;}publicvoidnext(){while(==null||!.()){try{=newStringTokenizer(.());}catch(IOException){thrownewRuntimeException();}}}publicint(){next();returnInteger.(.());}}classArrayUtils{publicstaticvoid(long[][],long){for(long[]:)Arrays.(,);}publicstaticvoid(long[][][],long){for(long[][]:)(,);}publicstaticvoid(long[][][][],long){for(long[][][]:)(,);}}

H题:题目看不懂怎么办。。。。。。。

J题: 求0到10^n中有多少个数满足被一些特定的数整除以及不整除 ，特定的数为 1 2 3 4 5 6

有一点很重要，如果x满足条件，那么x+60也满足条件，所以我们只要算60以内有几个就ok了。

(a/b)%mod = a * b^(phi(mod)-1)%mod,前提是a能被b整除。。我数论弱成渣了，这个都忘了考虑。。。

const int mod  = 1e9+7;int flag[10];int sum[110];lld Pow(lld a,lld b,lld m){    lld ans = 1;    while(b) {        if(b&1) ans = ans * a % m;        b >>= 1; a = a * a % m;    }    return ans;}int main(){    //printf("%I64d\n",100*Pow(60,mod-2,mod)%mod);    int t;    lld n;    char s[10];    scanf("%d",&t);    while(t--)    {        scanf("%I64d",&n);        scanf("%s",s+1);        vector<int> num,dis;        memset(flag,-1,sizeof(flag));        for(int i = 1; s[i]; i++)        {            if(s[i] == '1') flag[i] = 1;            else if(s[i] == '0') flag[i] = 0;        }        bool canz = true;        bool cann = true;        for(int j = 1; j <= 6; j++) if(flag[j] == 0 ) canz = false;        for(int j = 1; j <= 6; j++) if(flag[j] == 1) {            if((Pow(10,n,j)) != 0) cann = false;        } else if(flag[j] == 0) {            if((Pow(10,n,j)) == 0) cann = false;        }        for(int i = 1; i <= 60; i++)        {            bool f = true;            for(int j = 1; j<= 6; j++)            {                if(flag[j] == 1) {                    if(i % j != 0)  f = false;                } else if(flag[j] == 0){                    if(i % j == 0) f = false;                }            }        //  if(f) printf("i=%d\n",i);            sum[i] = sum[i-1];            if(f) sum[i]++;        }    //  printf("%d\n",sum[60]);        lld mx = Pow(10,n,mod);         if(n == 1) {            printf("%d\n",sum[9]+canz);        } else {            lld ans = 0;            lld l= Pow(10,n,60);            ans += sum[l];            ans %= mod;            mx -= l;            mx = (mx%mod + mod ) % mod;            ans += mx * Pow(60,(lld)mod-2,(lld)mod) % mod  * sum[60] % mod ;            //printf("ans=%I64d\n",ans);            ans %= mod;            printf("%I64d\n",(ans+canz-cann)%mod);        }    }    return 0;}

1楼azheng51714前天 08:19

求大神将AK 法典传授一下~~~

Re: haha593572013昨天 10:24

回复azheng51714n我是赛后默默补题的那种，所以我是小菜啊

Re: azheng51714昨天 11:47

回复haha593572013n你才大二，前途无量吖~~~~~~~~~~~~