Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing8 minutes read (About 1255 words)

【161016】ACM俱乐部区域赛前交流

  • 在线算法与离线算法

    假设举办江大程序设计校赛时要提供代码打印服务，通常情况下并发请求量并不大。
    我们的系统每接收到一条打印请求，就立即响应并指示打印机打出代码，这就是在线算法的工作策略。
    但在关键时刻可能会有大量请求蜂拥而来，服务器临时“宕机”了一下不能立即回应；请求就在缓冲池里堆积了起来。管理员看不下去了，马上出手打印了一大叠代码纸。这就好比是另一种工作策略——离线算法。

接着举例说明在线/离线的不同工作方式对算法设计的影响。

JNUOJ1150 线段覆盖

给出数轴上N条线段，每条线段用两个数表示A,B $ (-10^9 \leq A \lt B \leq 10^9) $ ，表示从a到b的一条线段。
现在请你求出它们覆盖数轴上的多长距离。

  • 空间中各个点的状态记录与增量记录
    这里有了个现成的数轴的概念，数轴是个一维空间，上面的各个位置具有被覆盖与不被覆盖两种状态。
    一条线段具有左端点和右端点两个属性，对左右端点之间各个位置产生状态改变。
    可以用一维数组记录（有需要知道的）各个位置的状态。考虑到同一个位置会被多条线段覆盖，那么修改增量（改变量）记录以便最终一次性更新。如果线段端点散步范围不大的话就这么做了。
    可是散布范围太大了，不论是评测机还是编译器都不会接受$ 10^9 $规模的数组。

  • 压缩空间
    并不是$ 10^9 $个位置都成为端点，可以作端点的位置至多$ 2N $个。
    要像制造“空间扭曲”一样缩短这个数轴，缩短遥远的端点之间的虚拟距离。
    现在把各个端点按照顺序映射到更紧密的空间上，也就是给每个位置按顺序分配一个虚拟ID。
    这样状态存储的空间就被压缩了，同时能够获知虚拟点之间的真实距离。

#include 
#include 
#include 

const int maxn=1000010;

int l[maxn],r[maxn],delta[maxn*2];

std::vector list;

int main(){
    int n;
    while(std::cin>>n){
        list.clear();
        std::fill(delta,delta+maxn*2,0);

        for(int i=0;i>l[i]>>r[i];
            list.push_back(l[i]);
            list.push_back(r[i]);
        }
        std::sort(list.begin(),list.end());
        list.erase(std::unique(list.begin(),list.end()),list.end());

        for(int i=0;i0)
                ans+=(i?list[i]-list[i-1]:0);
            cur+=delta[i];delta[i]=cur;
        }

        std::cout< 


    

  • 合并请求的离线化处理
    以上记录增量是拐弯抹角的解法，接下来说明“实用”的处理思路。
    线段跟线段肯定是有办法合并的，尽量把能合并的线段合成一条后取长度。
    每一轮合理的合并处理，可以从最左侧一条线段开始，向右逐个拼合，直到不能合并为止，取长度。反复进行这样的几轮处理。
    • 



const int maxn=1000010;

std::pair seg[maxn];

int main(){
    int n;
    while(std::cin>>n){
        for(int i=0; i>l>>r;
            seg[i]=std::make_pair(l,r);
        }
        std::sort(seg,seg+n);

        int ans=0,l=seg[0].first,r=seg[0].second;

        for(int i=0; i 



一维线性的问题可以拓展到二维平面上，长度被面积代替。


JNUOJ1147 Atlantis




已知平面上n个矩形，每个矩形用左上角、右下角的坐标确定，求合并后的总面积。  




    

  • 降维思路
    说的是二维，其实还是一维问题。矩形宽度（横向）视作线段宽度，高度（纵向）视作附加参数。
    线段仍然拆分成左右端点，不过引入新的概念，改叫左事件、右事件。
    • 



    

  • 步步为营
      扫描线每到一处，就生成并处理该处平行于扫描线方向上的一系列事件。
    • 



struct Rectangle{
    double x1,y1,x2,y2;
    Rectangle(double _x1,double _y1,double _x2,double _y2):x1(_x1),x2(_x2),y1(_y1),y2(_y2) {}
};
//通过左上角、右下角的坐标确定一个矩形
vector rects;
vector ylist;

double unionArea(const vector& rects,vector& ylist){
    if (rects.empty()) return 0;
    typedef pair > Event;
    vector events;

    ylist.clear();
    for(int i=0; i cnt(ylist.size()-1,0);
    //处理事件
    for(int i=0; i0)
                cutLength+=ylist[j+1]-ylist[j];
        res+=cutLength*(events[i+1].first-events[i].first);//乘上宽度值，得到面积
    }
    return res;
}

int main(int argc, char** argv){
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed,ios::floatfield);
    cout.precision(2);
    //设置实数输出格式

    int n,cas=0;
    while((cin>>n),n){
        rects.clear();
        for(int i=0; i>x1>>y1>>x2>>y2;
            rects.push_back(Rectangle(x1,y1,x2,y2));
        }
        cout<<"Test case #"<<++cas< 


    

  • 单点更新与批量查询
    

    • 

  • 区间更新与批量查询
    

    •
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 708 words)

hdu 2473 Junk-Mail Filter 并查集的删除操作

#Junk-Mail Filter

Time Limit: 15000/8000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

##Problem Description

Recognizing junk mails is a tough task. The method used here consists of two steps:

  1. Extract the common characteristics from the incoming email.
  2. Use a filter matching the set of common characteristics extracted to determine whether the email is a spam.

    We want to extract the set of common characteristics from the N sample junk emails available at the moment, and thus having a handy data-analyzing tool would be helpful. The tool should support the following kinds of operations:

a) “M X Y”, meaning that we think that the characteristics of spam X and Y are the same. Note that the relationship defined here is transitive, so
relationships (other than the one between X and Y) need to be created if they are not present at the moment.

b) “S X”, meaning that we think spam X had been misidentified. Your tool should remove all relationships that spam X has when this command is received; after that, spam X will become an isolated node in the relationship graph.

Initially no relationships exist between any pair of the junk emails, so the number of distinct characteristics at that time is N.
Please help us keep track of any necessary information to solve our problem.

##Input

There are multiple test cases in the input file.
Each test case starts with two integers, N and M (1 ≤ N ≤ 10^5 , 1 ≤ M ≤ 10^6), the number of email samples and the number of operations. M lines follow, each line is one of the two formats described above.
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.

##Output

For each test case, please print a single integer, the number of distinct common characteristics, to the console. Follow the format as indicated in the sample below.

##Sample Input

5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3

3 1
M 1 2

0 0

##Sample Output

Case #1: 3
Case #2: 2

#Source

2008 Asia Regional Hangzhou

  • 要删除结点时，原结点的编号作废但保留位置，再给该结点新分配一个“马甲”。
/**
 * Mar 28, 2016 8:25:14 PM
 * PrjName: fzu2155
 * @semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
    final static int maxn = 2000010;
    static int[] f = new int[maxn];
    static int[] g = new int[maxn];

    static int n, m, cnt;
    static Set st = new HashSet();

    static int getf(int x) {
        if (f[x] == x)
            return x;
        f[x] = getf(f[x]);
        return f[x];
    }

    static boolean unite(int x, int y) {
        int a = getf(g[x]);
        int b = getf(g[y]);
        if (a == b)
            return false;
        f[a] = b;
        return true;
    }

    static void init() {
        cnt = n;
        for (int i = 0; i < n + m; i++)
            f[i] = i;
        for (int i = 0; i < n; i++)
            g[i] = i;
    }

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int cas = 0;
        while (in.nextLine() != null) {
            n = in.nextInt();
            m = in.nextInt();
            if (n == 0 && m == 0)
                break;
            init();
            for (int i = 1; i <= m; i++) {
                String s = in.next();
                if (s.charAt(0) == 'M') {
                    int x = in.nextInt();
                    int y = in.nextInt();
                    unite(x, y);
                } else if (s.charAt(0) == 'S') {
                    int x = in.nextInt();
                    g[x] = cnt++;
                }
            }
            st.clear();
            for (int i = 0; i < n; i++)
                st.add(getf(g[i]));

            out.println("Case #" + (++cas) + ": " + st.size());
        }
        out.flush();
        out.close();
    }

}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String nextLine() {
        String tmp = null;
        try {
            tmp = reader.readLine();
            tokenizer = new StringTokenizer(tmp);
        } catch (IOException e) {
            throw new RuntimeException(e);
        } catch (NullPointerException e) {
            return null;
        }
        return tmp;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 55 words)

EC-final赛前一周

为信仰充值，与神犇赛码！年度最终决战，剑不出鞘更待何时？下周末双日，12.12～13，2015 ACM/ICPC EC-final 上海大学站，蓄势待发！全力备战

wpid-screenshot_2015-12-05-21-55-28.png wpid-230c7f4a3a36cc1f.jpg wpid-351324c2c7cdabb1.jpg wpid-screenshot_2015-12-05-21-55-05.png

wpid-screenshot_2015-12-05-22-02-33.png wpid-img_20151205_220342.jpg

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 472 words)

2015 ACM/ICPC Asia Regional Shenyang Online

Show All Problems

Soluble Problems
Jesus Is Here

Jesus Is Here

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/** Sep 19, 2015 12:41:25 PM
 * PrjName:0919-10
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static long[] s,l,f,ans;
    static String[] sh,sr;
    final static int maxn=201315;
    final static long mod=530600414L;
    static long mul_mod(long n, long m, long mod) {
        long ans = 0L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                ans = (ans + n) % mod;
            m >>= 1;
            n = (n + n) % mod;
        }
        return ans;
    }
    static void init(){
        s=new long[maxn];
        l=new long[maxn];
        f=new long[maxn];
        ans=new long[maxn];
        sh=new String[maxn];
        sr=new String[maxn];
        s[1]=s[2]=0;s[3]=1;s[4]=3;
        f[1]=f[2]=0;f[3]=f[4]=1;
        l[1]=1;l[2]=2;l[3]=3;l[4]=5;
        ans[1]=ans[2]=ans[3]=ans[4]=0;
        sh[3]=new String("cf");sr[3]=new String("ff");
        sr[4]=new String("ff");sr[4]=new String("ff");
    }
    static long solve(int n/*,PrintWriter out*/){
        long res=0L;
        if (n<5) return res;
        if (ans[n]>0L) return ans[n];
        res+=solve(n-2);
        res+=solve(n-1);
        //res+=solve(n-2,out);
        //res+=solve(n-1,out);
        sh[n]=sh[n-2];sr[n]=sr[n-1];
        boolean has=false;
        if (sr[n-2].compareTo("cf")==0&&sh[n-1].charAt(0)=='f'){
            has=true;s[n]+=l[n-2]-1;
            res-=s[n-2];
            res+=mul_mod((l[n-2]-1),f[n-2],mod);
        }
        if (sr[n-2].charAt(1)=='c'&&sh[n-1].compareTo("ff")==0){
            has=true;s[n]+=l[n-2];
            res-=s[n-2];
            res+=mul_mod(l[n-2],f[n-2],mod);
        }
        s[n]+=(s[n-2]+s[n-1]+mul_mod(l[n-2],f[n-1],mod))%mod;s[n]%=mod;
        f[n]=has?f[n-2]+f[n-1]+1:f[n-2]+f[n-1];f[n]%=mod;
        l[n]=l[n-2]+l[n-1];l[n]%=mod;
        //out.print(n+":");out.print(res+" ");
        res-=mul_mod(s[n-2],f[n-1],mod);//out.print(res+" ");
        //res+=s[n-1]*(has?f[n-2]+1:f[n-2]);out.print(res+" ");
        //res+=l[n-2]*f[n-1];out.println(res+" ");
        res+=mul_mod(s[n-1]+mul_mod(l[n-2],f[n-1],mod),f[n-2],mod);//out.println(res+" ");
        while(res<0L) res+=mod;
        //if (has) res+=
        res%=mod;
        ans[n]=res;
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        init();
        for(int i=5;i<maxn;i++)
            solve(i);
        while(T-->0){
            //long k=solve(in.nextInt(), out);
            long k=solve(in.nextInt());
            out.println("Case #"+(++cas)+": "+k);
        }
        out.flush();
        out.close();
    }
}

就差一点了，只剩减法取模的方法不太科学。
递归形式有利于寻找思路，改写成非递归形式更简练。

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 792 words)

2015 ACM/ICPC Asia Regional Changchun Online

Show All Problems

Soluble Problems
Alisha’s Party
Unknown Treasure

Alisha’s Party

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/** Sep 13, 2015 12:39:06 PM
 * PrjName:0913-01
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
	static Person[] per;
	static Pair[] cm;
	static PriorityQueue<Person> que = new PriorityQueue<Person>(new Person.Comp());
	static Vector<String> ans = new Vector<String>();

	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();
			int q = in.nextInt();
			per = new Person[n];
			for (int i = 0; i < n; i++)
				per[i] = new Person(in.next(), in.nextInt(), i + 1);
			cm = new Pair[m];
			for (int i = 0; i < m; i++)
				cm[i] = new Pair(in.nextInt(), in.nextInt());
			Arrays.sort(cm, new Pair.Comp());
			que.clear();
			int t = 0;
			ans.clear();
			for (int i = 0; i < n; i++) {
				que.add(per[i]);
				if (t < m && cm[t].l == i + 1) {
					for (int j = 0; j < cm[t].r && !que.isEmpty(); j++)
						ans.add(que.poll().name);
					t++;
				}
			}
			while (!que.isEmpty())
				ans.add(que.poll().name);
			while (q-- > 0) {
				out.print(ans.get(in.nextInt() - 1) + (q > 0 ? " " : ""));
			}
			out.println();
		}
		out.flush();
		out.close();
	}
}

class Person {
	String name;
	int v, t;
	Person() {
	}
	Person(String _nm, int _v, int _t) {
		name = _nm;
		v = _v;
		t = _t;
	}
	static class Comp implements Comparator<Person> {
		public int compare(Person p1, Person p2) {
			if (p1.v == p2.v)
				return Integer.compare(p1.t, p2.t);
			return -Integer.compare(p1.v, p2.v);
		}
	}
}

class Pair {
	int l, r;
	Pair() {
	}
	Pair(int a, int b) {
		l = a;
		r = b;
	}
	static class Comp implements Comparator<Pair> {
		public int compare(Pair o1, Pair o2) {
			if (o1.l == o2.l)
				return Integer.compare(o1.r, o2.r);
			return Integer.compare(o1.l, o2.l);
		}
	}
}

能不能别再搞那个复杂的合并了啊……还有不要对空优先队列做push操作啊……

Unknown Treasure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/** Sep 13, 2015 9:26:58 AM
 * PrjName:0913-10
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

    final static int maxn = 110000;
    static long[] fac = new long[maxn];
    static long[] p, a;
    static long x, y;

    static void Get_Fac(long n) {
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i;
            fac[i] %= n;
        }
    }

    static void extgcd(long a, long b) {
        if (b == 0L) {
            x = 1L;
            y = 0L;
            return;
        }
        extgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
    }

    static long pow_mod(long n, long m, long mod) {
        long res = 1L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                res = res * n % mod;
            n = n * n % mod;
            m >>= 1;
        }
        return res;
    }

    static long mul_mod(long n, long m, long mod) {
        long ans = 0L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                ans = (ans + n) % mod;
            m >>= 1;
            n = (n + n) % mod;
        }
        return ans;
    }

    static long div_mod(long n, long m, long mod) {
        return n * pow_mod(m, mod - 2, mod) % mod;
    }

    static long C(long n, long m, long mod) {
        int a = (int) (n % mod), b = (int) (m % mod);
        return div_mod(fac[a], mul_mod(fac[a - b], fac[b], mod), mod);
    }

    static long Lucas(long n, long m, long mod) {
        long ret = 1L;
        while (n > 0L && m > 0L) {
            if (n % mod < m % mod)
                return 0L;
            ret = mul_mod(ret, C(n, m, mod), mod);
            ret %= mod;
            n /= mod;
            m /= mod;
        }
        return ret;
    }

    // 中国剩余定理 x == a[i] (mod m[i]) 共有n个方程。
    static long CRT(long n, long[] a, long[] m) {
        long pro = 1L, res = 0L;
        for (int i = 0; i < n; i++)
            pro *= m[i];
        for (int i = 0; i < n; i++) {
            long w = pro / m[i];
            extgcd(m[i], w);
            res = (res + mul_mod(y, mul_mod(w, a[i], pro), pro)) % pro;
        }
        return (res + pro) % pro;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int T = in.nextInt();
        while (T-- > 0) {
            long n = in.nextLong();
            long m = in.nextLong();
            long num = in.nextLong();
            p = new long[15];
            a = new long[15];
            for (int i = 0; i < num; i++)
                p[i] = in.nextLong();
            for (int i = 0; i < num; i++) {
                Get_Fac(p[i]);
                a[i] = Lucas(n, m, p[i]);
            }
            out.println(CRT(num, a, p));
        }
        out.flush();
        out.close();
    }

}

一堆数论模板的集体亮相……但是为何解n个方程的中国剩余定理模板就难以被收集？

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 531 words)

2013 ACM/ICPC Asia Regional Chengdu Online

1007 F(x)数位DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/** Aug 22, 2015 5:23:42 PM
 * PrjName:hdu4734
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[][] f;
    static int[] digit;
    final static int maxm=4600;
    static int fun(int n){
        int res=0,tmp=1;
        while(n>0){
            res+=n%10*tmp;
            tmp<<=1;
            n/=10;
        }
        return res;
    }
    static void init(){
        int tmp=1;
        f=new int[10][maxm+1];
        f[0][0]=1;
        for(int i=1;i<10;i++){
            for(int j=0;j<=maxm;j++)
                for(int k=0;k<=9;k++)
                    if (j+tmp*k<=maxm)
                        f[i][j+tmp*k]+=f[i-1][j];
            tmp<<=1;
        }
        for(int i=0;i<10;i++)
            for(int j=1;j<=maxm;j++) f[i][j]+=f[i][j-1];
    }
    static int[] getdg(int n){
        int[] res=new int[10];
        while(n>0){
            res[++res[0]]=n%10;
            n/=10;
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        init();
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int A=in.nextInt();
            int B=in.nextInt();
            int m=fun(A);
            digit=getdg(B);
            int ans=0,tmp=1<<digit[0];
            for(int i=digit[0];i>=1;i--){
                tmp>>=1;
                for(int k=0;k<digit[i];k++){
                    
                    if (m-k*tmp>=0){
                        ans+=f[i-1][m-k*tmp];
                    }
                }
                m-=digit[i]*tmp;
                if (m<0) break;
                
            }
            if (m>=0) ans++;
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

磕磕绊绊的，到底有几大难？
期初是有过转化为背包问题的尝试，但是忽视了数位DP的处理手段；可先扩大枚举范围，再从中筛选。
预处理的两套循环不能杂糅在一起，因为先通过递推求了第i位、限制F(x)==j的解，然后才相加得到第i位、限制F(x)≤j的解。
筛选时注意“小于”的枚举方式。
最后还应留意B为可行解的条件。

1010 A Bit Fun

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/** Aug 22, 2015 4:28:18 PM
 * PrjName:hdu4737
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[] a;
    static Queue<Integer> que=new LinkedList<Integer>();
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        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];
            que.clear();
            int ans=0;
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                int k=que.size();
                for(int j=0;j<k;j++){
                    int tmp=que.poll()|a[i];
                    if (tmp<m) que.add(tmp);
                }
                if (a[i]<m) que.add(a[i]);
                ans+=que.size();
            }
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

并没有实现有些题解中所说的O(nlogn)或O(30n)的算法，但总的运行时间还是较短的？

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 277 words)

hdu 5115 Dire Wolf 区间DP

2014ACM/ICPC亚洲区北京站
Dire Wolf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * 2015年7月18日 上午9:55:52
 * PrjName:hdu5115
 * @ Semprathlon
 */
import java.io.*;
public class Main {
    final static long inf=0x7FFFFFFFFFFFFFFFL;
    static long min(long a,long b){
        return Math.min(a, b);
    }
    public static void main(String[] args)  throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int T=(int)in.nval,cas=0;
        int[] a,b;
        long[][] f;
        while(T-->0){
            in.nextToken();
            int n=(int)in.nval;
            a=new int[n+2];
            b=new int[n+2];
            f=new long[n+2][n+2];
            for(int i=1;i<=n;i++){
                in.nextToken();
                a[i]=(int)in.nval;
            }
            for(int i=1;i<=n;i++){
                in.nextToken();
                b[i]=(int)in.nval;
            }
            f[1][1]=a[1]+b[2];
            f[n][n]=a[n]+b[n-1];
            for(int i=2;i<n;i++)
                f[i][i]=a[i]+b[i-1]+b[i+1];
            for(int i=1;i<=n;i++)
                for(int j=i+1;j<=n;j++)
                    f[i][j]=inf;
            for(int j=0;j<=n;j++)
                for(int i=1;i+j<n+1;i++)
                    for(int k=i;k<=i+j;k++){
                        f[i][i+j]=min(f[i][i+j],f[i][k-1]+f[k+1][i+j]+a[k]+b[i-1]+b[i+j+1]);
                        //out.print(f[i][i+j]+" ");
                    }
            /*for(int i=0;i<=n+1;i++){out.println();
                for(int j=0;j<=n+1;j++)
                    out.print(f[i][j]+"\t");    
            }*/
                        
            
            /*for(int i=0;i<n;i++)
                for(int j=1;j<n-i;j++){
                    if (j==1)
                        min(f[j][j+i],f[j+1][j+i]+a[j]);
                    if (j>1)
                        min(f[j][j+i],f[j+1][j+i]+a[j]+b[j-1]);
                    if (i+j<n)
                        min(f[j][j+i],f[j][j+i-1]+a[j+i]+b[j+i+1]);
                    if (i+j==n)
                        min(f[j][j+i],f[j][j+i-1]+a[j+i]);
                    for(int k=j+1;k<j+i;k++)
                        min(f[j][j+i],f[j][k-1]+a[k]+f[k+1][j+i]);
                }*/
            out.println("Case #"+(++cas)+": "+f[1][n]);
            out.flush();
        }
        
        out.close();
    }
}

贪心真的是要贪婪死了。。。
已消除区段。。。其实对后续操作没有影响，符合无后效性。

Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×