2015 CCPC - 南阳站

这是一场炼狱般的较量。无心游玩，艰苦奋斗。

现场发挥	已解决题目
L - Huatuo’s Medicine	A - Secrete Master Plan
A - Secrete Master Plan	C - The Battle of Chibi
H - Sudoku	D - Pick The Sticks
D - Pick The Sticks(封榜后)	G - Ancient Go
H - Sudoku
Ranklist	L - Huatuo’s Medicine

L - Huatuo’s Medicine

认真阅读题目，并输出n*2-1.

A - Secrete Master Plan

将占据2*2点阵的四个整数进行旋转操作，写法较为多样化。
考验编码能力，准确、严谨、高效。消除毒代码。

inline LL fx(LL a1,LL a2,LL a3,LL a4){
    return a1*1000000000+a2*1000000+a3*1000+a4;
}

int main()
{
    int T,cas=0;
    cin>>T;
    while(T--){
        int a1,a2,a3,a4;
        cin>>a1>>a2>>a3>>a4;
        LL v0=fx(a1,a2,a4,a3);
        cin>>a1>>a2>>a3>>a4;
        LL v1=fx(a1,a2,a4,a3);
        LL v2=fx(a2,a4,a3,a1);
        LL v3=fx(a4,a3,a1,a2);
        LL v4=fx(a3,a1,a2,a4);
        //cout< 

H - Sudoku
简化的数独，规模为4*4，需填入1~4的整数。
/* 
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on November 8, 2015, 2:53 PM
 */

#include 
#include 
#include 

using namespace std;

char str[5];
int a[16],res[16],f[12];
bool ans;

void add(int x,int y,int v){
    a[x*4+y]=v;
    v=1<<(v-1);
    f[x]|=v;
    f[4+y]|=v;
    f[8+(x>1?2:0)+(y>1?1:0)]|=v;
}

void del(int x,int y,int v){
    a[x*4+y]=0;
    v=1<<(v-1);
    f[x]&=~v;
    f[4+y]&=~v;
    f[8+(x>1?2:0)+(y>1?1:0)]&=~v;
}

bool has(int x,int y,int v){
    v=1<<(v-1);
    return (f[x]&v)||(f[4+y]&v)||(f[8+(x>1?2:0)+(y>1?1:0)]&v);
}

bool check(){
    for(int i=0;i<12;i++)
        if (f[i]<15)
            return 0;
    return 1;
}

void solve(int x,int y){
    if (check()){
        for(int i=0;i<16;i++)
            res[i]=a[i];
        ans=1;
        
        return;
    }
    for(int i=x*4+y;i<16;i++)
        if (!a[i]&&!ans)
            for(int k=1;k<=4;k++)
                if (!has(i/4,i%4,k))
            {
                add(i/4,i%4,k);
                solve(i/4,i%4);
                del(i/4,i%4,k);
            }
}

int main(int argc, char** argv) {
    int T,cas=0;
    cin>>T;
    while(T--){
        fill(f,f+12,0);
        for(int i=0;i<4;i++){
            cin>>str;
            for(int j=0;j<4;j++)
                if (str[j]=='*')
                    a[i*4+j]=0;
                else
                    add(i,j,str[j]-'0');
        }
        ans=0;
        solve(0,0);
        printf("Case #%d:\n",++cas);
        for(int i=0;i<4;i++){
                for(int j=0;j<4;j++)
                    cout< 

D - Pick The Sticks
从若干个已知体积（即长度）与价值的物品中取一些装入已知长度的线性横杆状容器中使总价值最大。其长度和可超过容器长度，但是需保证每件物品的重心均在容器内。
设计巧妙的01背包问题变种，但是一开始当成贪心做了，之后又遗漏了一些转移方向，以至于拖到了封榜后。
思想是在原背包基础上新增一个状态参数，取值范围为{0,1,2}.
0表示不允许两端有物体超出。
1表示允许某一端有物体超出。
2表示两端都可以有物体超出。
/**
 * Dec 5, 2015 5:21:06 PM
 * PrjName: hdu5543
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int a[];
    static long v[],f[][];
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int n=in.nextInt();
            int l=in.nextInt();l<<=1;
            long maxv=0;
            a=new int[n+1];
            v=new long[n+1];
            f=new long[l+1][3];
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                v[i]=in.nextLong();
                a[i]<<=1;
                maxv=Math.max(maxv, v[i]);
            }
            for(int i=1;i<=n;i++)
                for(int j=l;j>=0;j--){
                    if (j>=a[i])
                        for(int k=0;k<3;k++)
                            f[j][k]=Math.max(f[j][k], f[j-a[i]][k]+v[i]);
                    if (j>=(a[i]>>1)){//可能遗漏
                        f[j][1]=Math.max(f[j][1], f[j-(a[i]>>1)][0]+v[i]);
                        f[j][2]=Math.max(f[j][2], f[j-(a[i]>>1)][1]+v[i]);
                    }
                }
            
            long ans=maxv;
            ans=Math.max(ans, f[l][0]);
            ans=Math.max(ans, f[l][1]);
            ans=Math.max(ans, f[l][2]);
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }
}
 

G - Ancient Go
阅读理解，试根据题中所给规则，判断当前围棋对局中黑方(x)再下一子后能否实现“吃子”。
当白方棋子(o)形成的某一连通块完全被对方包围（考虑4个方向）而没有与空点相邻时，就会被kill.
比赛中解题时，问题重点始终放在黑子上；枚举黑子可下的位置并填充颜色、验证。但是无解。
其实切入点应该转移到白子上；选定一个白连通块，查看包围它的黑子个数，判断是否即将封闭。
const int maxn=9;
const int dir[4][2]={ {-1,0},{1,0},{0,1},{0,-1}};

char s[maxn];
int g[maxn][maxn];
bool vis[maxn][maxn];

inline bool can(int x,int y){
    return x>=0&&x=0&&y>T;

    while(T--){
        for(int i=0;i 

C - The Battle of Chibi
public class Main {
    static int[][] f;
    static int[] a;
    final static int mod=1000000007;
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            a=new int[n+1];
            f=new int[n+1][m+1]; 
            for(int i=1;i<=n;i++)
                a[i]=in.nextInt();
            for(int i=1;i<=n;i++){
                f[i][1]=1;
                for(int j=1;j<=Math.min(i, m);j++){
                    for(int k=j-1;ka[k]){
                        f[i][j]+=f[k][j-1];
                        
                    }
                }
            }
            int ans=0;
            for(int i=m;i<=n;i++)
                ans=(ans+f[i][m])%mod;
            out.println(ans);
        }
        out.flush();
        out.close();
    }
}
 
三层循环超时，尝试消去一维。
/**
 * Mar 17, 2016 10:16:51 PM
 * PrjName: hdu5542
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int[][] f;
    static int[] a,b;
    final static int mod=1000000007;
    static int lowbit(int x){
        return x&(-x);
    }
    static void add(int x,int y,int v,int sz){
        while(x0){
            res+=f[x][y];
            res%=mod;
            x-=lowbit(x);
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            a=new int[n+1];
            f=new int[n+1][m+1]; 
            for(int i=1;i<=n;i++)
                a[i]=in.nextInt();
            b=a.clone();
            Arrays.sort(b);
            for(int i=1;i<=n;i++)
                a[i]=Arrays.binarySearch(b, a[i]);
            for(int i=1;i<=n;i++){
//                f[i][1]=1;
                add(a[i], 1, 1, n+1);
                for(int j=2;j<=Math.min(i, m);j++){
                    int tmp=sum(a[i]-1,j-1);
                    add(a[i], j, tmp, n+1);
                    /*for(int k=0;ka[k]){
                        f[i][j]+=f[k][j-1];
                        f[i][j]%=mod;
                    }*/
                    //f[i][j]%=mod;
                }
            }
            /*for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++)
                    out.print(f[i][j]+" ");
                out.println();
            }*/
            /*int ans=0;
            for(int i=1;i<=n;i++)
                ans=(ans+f[i][m])%mod;*/
            out.println("Case #"+(++cas)+": "+sum(n, m));
        }
        out.flush();
        out.close();
    }

}