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

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

比赛地址

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

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

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

B题：

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

#include<cstdio>
#include<cstring>
#define L ch[x][0]
#define R ch[x][1]
#define KT (ch[ ch[rt][1] ][0])
const int maxn = 200010;
struct SplayTree {
    int sz[maxn];
    int ch[maxn][2];
    int pre[maxn];
    int rt,top;
    inline void up(int x){
        sz[x]=1+sz[ L ] + sz[ R ];
    }
    inline void Rotate(int x,int f){
        int y=pre[x];
        ch[y][!f] = ch[x][f];
        pre[ ch[x][f] ] = y;
        pre[x] = pre[y];
        if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] =x;
        ch[x][f] = y;
        pre[y] = x;
        up(y);
    }
    inline void Splay(int x,int goal){//将x旋转到goal的下面
        while(pre[x] != goal){
            if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][0] == x);
            else   {
                int y=pre[x],z=pre[y];
                int f = (ch[z][0]==y);
                if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f);
                else Rotate(y,f),Rotate(x,f);
            }
        }
        up(x);
        if(goal==0) rt=x;
    }
    inline void RTO(int k,int goal){//将第k位数旋转到goal的下面
        int x=rt;
        while(sz[ L ]+1 != k) {
            if(k < sz[ L ] + 1 ) x=L;
            else {
                k-=(sz[ L ]+1);
                x = R;
            }
        }
        Splay(x,goal);
    }
    void vist(int x){
        if(x){
            vist(L);
            printf("%c " ,val[x]);
            vist(R);
        }
    }
    void Newnode(int &x,char c,int f){
        x=++top;   
        L = R = 0; pre[x]=f;
        sz[x]=1; val[x] = c; 
    }
    inline void build(int &x,int l,int r,int f){
        if(l>r) return ;
        int m=l+r>>1;
        Newnode(x,s[m],f);
        build(L , l , m-1 , x);
        build(R , m+1 , r , x);
        pre[x]=f;
        up(x);
    }
    inline void init(int n){
        ch[0][0]=ch[0][1]=pre[0]=sz[0]=0;
        rt=top=0; val[0] = '@';
        Newnode(rt,'@',0);
        Newnode(ch[rt][1],'@',rt);
        sz[rt] = 2;
        build(KT,1,n,ch[rt][1]);
        //vist(rt);
    }
    void gao(int pos,char c) // 将c插入到第pos个元素之前
    {
    /// printf("pos=%d \n",pos);
        RTO(pos,0);
        RTO(pos+1,rt);
        Newnode(KT,c,ch[rt][1]);
    }
    void print(int pos) // 输出第pos个字符
    {
        //printf("pos=%d\n",pos);
        RTO(pos+1,0); 
        printf("%c",val[rt]);
    }
    void prepare()
    {
        scanf("%s",s+1);
        int len = strlen(s+1);
        init(len);
    }
    void solve()
    {
        char op[10];
        int pos ,begin , end;
        while(scanf("%s",op)!=EOF){
            if(strcmp(op,"END") == 0) break;
            if(op[0] == 'I') {
                scanf("%s%d",str,&pos);
                int len = strlen(str);
                for(int i = 0; i < len; i++) {
                    gao(pos+1+i,str[i]) ; 
                }
            } 
            else {
                scanf("%d%d",&begin,&end);
                begin ++ , end ++;
                for(int i = begin; i <= end; i++) {
                    print(i);
                }
                puts("");
            }
        }
    }
    char str[maxn];
    char val[maxn];
    char s[maxn];
}spt;
int main()
{
    spt.prepare();
    spt.solve();
    return 0;
}

E题：

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

#include<stdio.h>
#include<string.h>
const int MAX=1010;
const int INF=1000000000;
struct
{
    int v,c,next;
}edge[1000000];
int E,head[MAX];
int gap[MAX],cur[MAX];
int pre[MAX],dis[MAX];
void add_edge(int s,int t,int c,int cc)
{
    /*加边的时候同时加两条，
    一条正的，一条反的，
    一般情况下反的容量是0 */
    edge[E].v=t; edge[E].c=c;
    edge[E].next=head[s];
    head[s]=E++;
    edge[E].v=s; edge[E].c=cc;
    edge[E].next=head[t];
    head[t]=E++;
}
int min(int a,int b){return (a==-1||b<a)?b:a;}
int SAP(int s,int t,int n)
{
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    int i;
    for(i=0;i<n;i++)cur[i]=head[i];
    int u=pre[s]=s,maxflow=0,aug=-1,v;
    gap[0]=n;   
    while(dis[s]<n)
    {
loop:   for(i=cur[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].v;
            if(edge[i].c>0&&dis[u]==dis[v]+1)
            {
                aug=min(aug,edge[i].c);
                pre[v]=u;
                cur[u]=i;
                u=v;
                if(u==t)
                {
                    for(u=pre[u];v!=s;v=u,u=pre[u])
                    {
                        edge[cur[u]].c-=aug;
                        edge[cur[u]^1].c+=aug;
                    }
                    maxflow+=aug;
                    aug=-1;
                }
                goto loop;
            }
        }
        int mindis=n;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].v;
            if(edge[i].c>0&&dis[v]<mindis)
            {
                cur[u]=i;
                mindis=dis[v];
            }
        }
        if((--gap[dis[u]])==0)break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return maxflow;
}
char str[110][10];
bool vis[110][26];
int ID[500];
char now[110] ; 
int tot ;
int cnt[26];
int len ;
int S,T;
bool Replay()
{
    memset(head,-1,sizeof(head));
    E=0;
    for(int i = 1; i <= 26; i++) if(cnt[i-1]){
    //  printf("%d %d\n",S,i);
        add_edge(S,i,cnt[i-1],0);
    }
    for(int i = 1; i <= len; i++)
    {
        if(i <= tot)
        {
            add_edge(now[i]-'a'+1,i+26,1,0);
        }
        else 
        {
            for(int j = 0; str[i][j]; j++)
            {
                add_edge(str[i][j]-'a'+1,i+26,1,0);
            }
        }
    }
    for(int i = 1; i <= len; i++) add_edge(i+26,T,1,0);
    return  ( SAP(S,T,T+1) == len );
}
bool solve()
{
    tot = 0;
    if(!Replay()) return false;
    for(int i = 1; i <= len;i++)
    {
         for(int j = 0; j < 26; j++)if(vis[i][j])
         {
             now[i] = 'a' + j;
             tot = i;
             if(Replay()) break;
         }
    }
    return true;
}
int main()
{
    char s[110];
    scanf("%s",s+1);
    len = strlen(s+1); 
    for(int i = 1; i <= len; i++) cnt[s[i]-'a'] ++;
    S = 0 , T = 26 + len + 1;
    for(int i = 1; i <= len; i++)   
    {
        scanf("%s",str[i]);
        for(int j = 0; str[i][j]; j++)
        {
            vis[i][str[i][j]-'a'] = true;
        }
    }
    if(!solve())  puts("NO SOLUTION");
    else {
        for(int i = 1; i < len; i++) printf("%c",now[i]);printf("%c\n",now[len]);
    }
    return 0;
}

G题：

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

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

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

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

import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AC solver = new AC();
        solver.solve(in, out);
        out.close();
    }
}

class AC {
    long dp[][][][] = new long[5][5][60][1 << 12];
    int vis[][] = new int[10][10];
    int state[][] = new int[10][10];
    int L;
    public void solve(InputReader in, PrintWriter out) {
        int N, x, y;
        L = in.nextInt();
        N = in.nextInt();
        for(int i = 1; i <= 3; i++) Arrays.fill(vis[i],0);
        for (int i = 0; i < N; i++) {
            x = in.nextInt();
            y = in.nextInt();
            vis[x][y] = 2;
        }
        if (L > 55) {
            out.println("BAD MEMORY");
        } else {
            ArrayUtils.fill(dp,-1);
            long ans = 0;
            for (int i = 1; i <= 3; i++) {
                for (int j = 1; j <= 4; j++)
                    if (vis[i][j] != 2) {
                        int id = (j - 1) * 3 + i;
                        state[i][j] = (1 << (id - 1));
                    }
            }
            for (int i = 1; i <= 3; i++) {
                for (int j = 1; j <= 4; j++)
                    if (vis[i][j] != 2) {
                        vis[i][j] = 1;
                        ans += dfs(i, j, L, state[i][j]);
                        //out.println(ans);
                        vis[i][j] = 0;
                        //return ;
                        
                    }
            }
            if(ans!=0)out.println(ans);
            else out.println("BAD MEMORY");
        }
    }

    private long dfs(int x, int y, int len, int mask) {
        if (len < 0)  return 0;
        if (dp[x][y][len][mask] != -1)
            return dp[x][y][len][mask];
        if (len == 0)
            return dp[x][y][len][mask] = 1;
        dp[x][y][len][mask] = 0;
        
        for (int a = 1; a <= 3; a++) {
            for (int b = 1; b <= 4; b++) {
                if (a == x && b == y || vis[a][b] != 0)
                    continue;
                boolean cango = true;
                if (Math.abs(x - a) % 2 == 0 && Math.abs(y - b) % 2 == 0) {
                    int tx = Math.abs(x + a) / 2;
                    int ty = Math.abs(y + b) / 2;
                    if (vis[tx][ty] == 0 || vis[tx][ty]==2) cango = false;
                }
                if(x == a) {
                    for(int i = Math.min(y, b)+1; i <= Math.max(y,b)-1; i++) {
                        if(vis[x][i] == 0 || vis[x][i] == 2) cango = false;
                    }
                }
                if(!cango) continue;
                vis[a][b] = 1;
                dp[x][y][len][mask] += dfs(a, b, len - (Math.abs(x - a) + Math.abs(y - b)),mask | state[a][b]);
                vis[a][b] = 0;
            }
        }
        return dp[x][y][len][mask];
    }
}

class InputReader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    public void next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }
    public int nextInt() {
        next();
        return Integer.parseInt(tokenizer.nextToken());
    }
}
class ArrayUtils {
    public static void fill(long[][] array, long value) {
        for (long[] row : array)
            Arrays.fill(row, value);
    }
    public static void fill(long[][][] array, long value) {
        for (long[][] row : array)
            fill(row, value);
    }
    public static void fill(long[][][][] array, long value) {
        for (long[][][] row : array)
            fill(row, value);
    }
}

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 法典传授一下~~~

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

相关推荐