Shen Huang's Blog
0%

Posted on Edited on

A题是POJ1091

B题是POJ1141

A

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
//假设卡片上标号分别A1,A2,...,An,M，跳蚤跳对应号的次数分别是X1,X2,...,Xn,跳M个单位长度的次数是Xn-1,那么要满足一直条件只需满足方程Xn+1A1X1+A2X2+...+AnXn+M X^(n+1)=1有解，即（A1,A2,...,An,M）=1,接下来对M分解，然后排除共因子不是1的情况即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define LL long long
using namespace std;

const int N=64;
int bo[N],t;
void divide(int m){
    int i;
    t=0;
    for(i=2;i*i<=m;i++){
        if(m%i==0){
            t++;
            bo[t]=i;
            while(m%i==0) m/=i;
        }
    }
    if(m!=1){
        t++;
        bo[t]=m;
    }
}
LL quick_multi(LL a,LL b){//普通求幂
    LL ans=1;
    while(b){
        ans*=a;
        b--;
    }
    return ans;
}

LL ans,tmp;
int a[N],m,n;

void dfs(int b,int ct,int c){
    int i,x;
    if(ct==c){
        x=m;
        for(i=1;i<=c;i++)
            x/=a[i];
        tmp+=quick_multi(x,n);
        return;
    }
    for(i=b+1;i<=t;i++){
        a[ct+1]=bo[i];
        dfs(i,ct+1,c);
    }
}

int main(){
    int T,i;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        ans=t=0;
        divide(m);
        for(i=1;i<=t;i++){
            tmp=0;
            dfs(0,0,i);
            if(i&1) ans+=tmp;
            else ans-=tmp;
        }
        ans=quick_multi(m,n)-ans;
        printf("%I64dn",ans);
    }
    return 0;
}

B

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 9831892
int dp[105][105];
int main()
{
    int n,i,j,k,p;
    char s[105];
    scanf("%d",&n);
    while(n--)
    {
        getchar();
        scanf("%s",s);
        int l=strlen(s);
        memset(dp,0,sizeof(dp));
        for(i=0;i<l;i++) dp[i][i]=1;
        for(p=1;p<l;p++)
        {
            for(i=0;i<l-p;i++)
            {
                j=i+p;
                dp[i][j]=inf;
                if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']&#39;))
                    dp[i][j]=min(dp[i][j],dp[i+1][j-1]);//如果匹配，取中间需要的括号；
                else if(s[i]=='['||s[i]==&#39;(&#39;)
                    dp[i][j]=min(dp[i][j],dp[i+1][j])+1;//如果是左括号，取其i+1~j位置需要括号最少的个数；
                else if(s[i]==')'||s[i]==']&#39;)
                    dp[i][j]=min(dp[i][j],dp[i][j-1])+1;//如果是右括号，取其i~j-1位置需要括号最少的个数；
                for(k=i;k<j;k++)
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);//分割求和比较最少需要括号的个数；
            }
        }
        printf("%dn",dp[0][l-1]);
    }
}

C

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
/* From: Lich_Amnesia
 * Time: 2014-04-10 19:56:22
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define pi 3.14159265358979323846
typedef struct  
{  
    double x;  
    double y;  
    double z;  
}air;
struct Edge{
    int u,v;
    double d;
}ed[50500];
air p[110];
int num;
#define EPS 1e-8

int pa[110];
bool cmp(Edge a,Edge b){
    return a.d  < b.d;
}

int find(int x){
    return (pa[x] == x) ? x: pa[x] = find(pa[x]);
}

double Kruskal(int n)
{
    double total = 0;
    //对n个顶点初始化并查集
    for(int i = 0;i < n;i++) 
        pa[i] = i;
    //初始化序号记录集
    sort(ed,ed + num,cmp);
    for(int i = 0;i < num;i++)//对每一条边来考查
    {
        int ru = find(ed[i].u);
        int rv = find(ed[i].v);
        if(ru != rv)
        {
            total += ed[i].d;
            pa[rv] = ru;
        } 
     }
     return total;
}

int main(){
    int T,n;
    scanf("%d", &T);
    double D,L;
    while (T--){
        scanf("%lf", &D);
        scanf("%lf", &L);
        scanf("%d", &n);
        double R = D / 2.0;
        double l,r;
        for (int i = 0; i < n; i ++){
            scanf("%lf %lf", &l, &r);
            l = l * pi/180.0;  
            r = r * pi/180.0;  
            //p[i].x = R*cos(l)*cos(r);  
            //p[i].y = R*cos(l)*sin(r);  
            //p[i].z = R*sin(l);  
            p[i].x = l;
            p[i].y = r;
        }
        num = 0;
        double c;
        for (int i = 0; i < n; i ++){
            for (int j = 0; j < n; j ++){
                if (i == j) continue;
                c = sin(p[i].x) * sin(p[j].x) + cos(p[i].x) * cos(p[j].x)
                    * cos(p[i].y - p[j].y);
                ed[num].u = i;
                ed[num].v = j;
                ed[num++].d = fabs(R * acos(c));
                //ed[num++].d = dis(p[i],p[j]);
            }
        }
        double ans = Kruskal(n);
        //acerr<<ans<<endl;
        if (ans - EPS < L) puts("Y");
        else puts("N");
    }
    return 0;
}

D

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
/* From: Lich_Amnesia
 * Time: 2014-04-10 19:36:37
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

unsigned long long fac[80];

void init(){
    fac[0] = 1;
    for (int i = 1; i < 64; i ++){
        fac[i] = fac[i - 1] * 2;
    }

}
typedef unsigned long long ull;
ull num[100];

bool cmp(ull a,ull b){
    return a < b;
}
int main(){
    int T;
    cin >> T;
    char s[100];
    ull n,m;
    init();
    while (T--){
        int cnt = 0;
        cin >> m >> n;
        ull now = m;int flag = 0;
        for (int i = 0; i < n; i ++){
            if (now & fac[n - 1]) flag = 1;
            else flag = 0;
            now &= (fac[n - 1] - 1);
            now <<= 1;
            now |= flag;
            num[i] = now;
        }
        sort(num,num + n,cmp);
        for (int i = 0; i < n; i ++){
            s[i] = (num[i] & 1) + &#39;0&#39;;
        }
        s[n] = 0;
        printf("%sn",s);
    }
    return 0;
}

Posted on Edited on

分组背包，finger先n^2预处理出来

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

char name[][100]={"Head", "Shoulder", "Neck", "Torso", "Hand", "Wrist", "Waist", 
"Legs", "Feet", "Shield", "Weapon", "Two-Handed", "Finger"};
int num[15],d[15][310],t[15][310],dp[15][50010];
char s[100];
int main(int argc, char const *argv[])
{
    int T,n,m;
    cin >> T;
    while (T--){
        memset(num,0,sizeof(num));
        cin >> n >> m;
        for (int i = 0; i < n; i ++){
            scanf("%s", s);
            int j;
            for (j = 0; ;j ++){
                if (strcmp(s,name[j]) == 0) break;
            }
            j ++;
            num[j] ++;
            scanf("%d%d", &d[j][num[j]], &t[j][num[j]]);
        }
        memset(dp,-1,sizeof(dp));
        dp[0][0] = 0;
        //注意每次都是从0到num[i]因为dp[i][j] = dp[i - 1][j]的就是说可能某个位置没有
        //预处理时候finger可以是0,1,2的混合
        //预处理出只有finger的情况
        for (int i = 0; i <= num[13]; i ++){
            for (int j = i + 1; j <= num[13]; j ++){
                dp[0][min(m,t[13][i] + t[13][j])] = max(dp[0][min(m,t[13][i] + t[13][j])],
                 d[13][i] + d[13][j]);
            }
        }

        for (int i = 1; i <= 11; i ++){
            for (int j = 0; j <= m; j ++){
                if (dp[i - 1][j] == -1) continue;
                for (int k = 0; k <= num[i]; k ++){
                    dp[i][min(m, j + t[i][k])] = max(dp[i][min(m, j + t[i][k])],
                     dp[i - 1][j] + d[i][k]);
                }
            }
        }
        //i - 1  = 9 在Feet i = 12
        for (int j = 0; j <= m; j ++){
            if (dp[9][j] == -1) continue;
            for (int k = 0; k <= num[12]; k ++){
                dp[11][min(m, j + t[12][k])] = max(dp[11][min(m, j + t[12][k])], 
                    dp[9][j] + d[12][k]);
            }
        }
        printf("%dn",max(-1,dp[11][m]));
    }
    return 0;
}

Posted on Edited on

看了ACdreamers的解题http://blog.csdn.net/acdreamers/article/details/23039571

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
/* From: Lich_Amnesia
 * Time: 2014-04-07 20:49:38
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

typedef long long ll;
#define maxn 100005
const ll mod = 1000000009;
ll fac[maxn],A[maxn],B[maxn];

void init(){
	fac[0] = 1;
	for (int i = 1; i < maxn; i ++){
		fac[i] = fac[i-1] * i % mod;
	}
	A[0] = B[0] = 1;
	for (int i = 1; i < maxn; i++){
		A[i] = A[i-1] * 691504013 % mod;
		B[i] = B[i-1] * 308495997 % mod;
	}
}

ll quick_mod(ll n,ll k,ll mod){
	ll ret = 1;
	n %= mod;
	while (k){
		if (k & 1) ret = ret * n % mod;
		k >>= 1;
		n = n * n % mod;
	}
	return ret;
}

ll solve(ll n, ll k){
	ll ret = 0;
	for (int r = 0; r <= k; r ++){
		ll t = A[k - r] * B[r] % mod;
		ll x = fac[k];
		ll y = fac[k-r] * fac[r] % mod;
		ll c = x * quick_mod(y, mod - 2, mod) % mod;
		ll tmp = t * (quick_mod(t, n, mod) - 1) % mod 
			* quick_mod(t-1,mod-2,mod) % mod;
		if (t == 1) tmp = n % mod;
		tmp = tmp * c % mod;
		if (r & 1) ret -= tmp;
		else ret += tmp;
		ret %= mod;
	}
	ll m = quick_mod(383008016,mod-2,mod);
	ret = ret * quick_mod(m,k,mod) % mod;
	ret = (ret % mod + mod) % mod;
	return ret;
}

int main(){
	int T;
	ll n,k;
	init();
	cin >> T;
	while (T--){
		cin >> n >> k;
		cout << solve(n,k) << endl;
	}
	return 0;
}

Posted on Edited on

2014 浙大校赛 F 单点更新线段树

把递推式子写成矩阵的形式，这样f[r]就相当于一个矩阵连成的形式

注意矩阵连乘时候的方向

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
/* From: Lich_Amnesia
 * Time: 2014-04-07 20:02:21
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define lson l, m , rt << 1
#define rson m + 1, r , rt << 1 | 1

#define maxn 400040
typedef long long ll;
#define mod 1000000007
struct mat{
	ll a[2][2];
	mat(){
		memset(a,0,sizeof(a));
	}
	mat(ll x){
		a[0][0] = a[1][0] = 1;
		a[1][1] = 0;
		a[0][1] = x;
	}
	mat operator * (const mat &b) const{
		mat ret = mat();
		for (int i = 0; i < 2; i ++){
			for (int j = 0; j < 2; j ++){
				for (int k = 0; k < 2; k ++){
					ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod;
				}
			}
		}
		return ret;
	}
};

ll num[maxn];
mat sum[maxn];

void PushUp(int rt){
	sum[rt] = sum[rt << 1 | 1] * sum[rt << 1];//会不会有问题
}

void build(int l, int r, int rt){
	if (l == r) {
		sum[rt] = mat(num[l]);
		return;
	}
	int m = MID(l,r);
	build(lson);
	build(rson);
	PushUp(rt);
}

mat query(int L,int R, int l, int r, int rt){
	if (L <= l && r <= R) return sum[rt];
	int m = MID(l, r);
	if (R <= m) return query(L, R, lson);//lson包括mid
	if (L > m) return query(L, R, rson);//rson从mid+1开始
	return query(L,R,rson) * query(L,R,lson);//会不会反了
}

int main(){
	int T,n,m;
	cin >> T;
	mat t;
	while (T--){
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i ++){
			scanf("%lld", &num[i]);
		}
		build(1, n, 1);
		int l,r;
		for (int i = 0; i < m; i ++){
			scanf("%d%d", &l, &r);
			if (l == r || r == l + 1){
				printf("%lldn", num[r]);continue;
			}
			t = query(l + 2,r,1,n,1);
			printf("%lldn", (t.a[0][0] * num[l + 1] + t.a[0][1] * num[l]) % mod);
		}
	}
	return 0;
}

Posted on Edited on

2014 浙大校赛 I

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
/* From: Lich_Amnesia
 * Time: 2014-04-06 14:00:10
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

char str[20] = "Hello, world!";
int main(){
	int t;
	cin >> t;
	getchar();	
	char s1[300],s2[3000];
	while (t--){
		int cnt = 0;
		cin.getline(s1,256);
		int len1 = strlen(s1);
		bool flag = 1;
		for (int i = 0; i < len1; i ++){
			if (cnt > len1) {flag = 0;break;}
			if (s1[i] == &#39;_&#39;){
				for (int j = 0; j < len1; j ++){
					s2[cnt ++] = s1[j];
				}
			}
			if (s1[i] == &#39;!&#39;){
				for (int j = 0; j < strlen(str); j ++){
					s2[cnt ++] = str[j];
				}
			}
		}
		if (cnt != len1) flag = 0; 
		if (flag){
			for (int i = 0; i < len1; i ++){
				if (s1[i] != s2[i]) {flag = 0;break;}
			}
		}
	//	cout << s1 << " s2: "<< s2 << endl;
		if (!flag){
			puts("No");
		}else puts("Yes");
	}
	return 0;
}

Posted on Edited on

2014 浙大校赛 D 排序题

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
/* From: Lich_Amnesia
 * Time: 2014-04-06 14:17:00
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
struct Info{
	int i,id,day,va;
}p[2200];
int le[2200];
bool cmp(Info a,Info b){
	if (a.va == b.va){
		if (a.day == b.day){
			return a.id < b.id;
		}else return a.day < b.day;
	}else return a.va > b.va;
}
double val[10] = {0,0,0.4,0.3,0.2,0.07,0.03};
int main(){
	int t;
	cin >> t;
	int n,day,mon,year;
	while (t--){
		int nozero = 0;
		scanf("%d", &n);
		memset(le,-1,sizeof(le));
		for (int i = 0; i < n; i ++){
			scanf("%d", &p[i].id);
			scanf("%d/%d/%d", &year, &mon, &day);
			p[i].day = year * 10000 + mon * 100 + day;
			scanf("%d", &p[i].va);
			p[i].i = i;
			if (p[i].va > 0){ nozero ++;
				le[i] = 2;
			}
			if (p[i].va == 0) le[i] = 1;
		}
		sort(p,p + n,cmp);
		//for (int i = 0; i < n; i ++){
		//	cout << p[i].i << ' ' << p[i].id << ' '<< p[i].day<< ' ' << p[i].va << endl;
		//}
		int cnt = 0;
		for (int k = 6; k > 1; k --){
			int now = val[k] * nozero;
			while (now){
				le[p[cnt].i] = k;
				cnt ++;
				now --;
			}
		}
		for (int i = 0; i < n; i ++){
			printf("LV%dn",le[i]);
		}
	}
	return 0;	
}

Posted on Edited on

2014 浙大校赛 B

其实就是找到规律最多只可能是1，2，3种分割

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
/* From: Lich_Amnesia
 * Time: 2014-04-07 11:22:09
 *
 * ZOJ 3768
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

int check(int n){
	int k = max(0,(int)sqrt(2 * n) - 4);
	for (int i = k; i * i <= 2 * n; i ++){
		if (i * i  + i == 2 * n) return i;
	}
	return 0;
}

int main(){
	int T,n;
	cin >> T;
	while (T--){
		scanf("%d", &n);
		int l,k = check(n);
		if (k){
			printf("%dn", k);
		}else {
			bool flag = 0;
			for (int i = 1; i * i + i <= 2 * n; i ++){
				l = check(n - (i + 1) * i /2);
				if (l){
					printf("%d %dn", i, l);
					flag = 1;
					break;
				}
			}
			if (!flag){
				for (int i = 1; i * i + i <= 2 * n && !flag; i ++){
					int mod = n - (i + 1) * i / 2;
					for (int j = 1; j * (j + 1) / 2 <= mod && !flag; j ++){
						l = check(n - (j*(j+1)/2) - i * (i + 1) /2);
						if (l){
							printf("%d %d %dn", i, j ,l);
							flag = 1;
							break;
						}
					}
				}
			}
		}
	}
	return 0;
}

Posted on Edited on

2014年浙大校赛 A

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
/* From: Lich_Amnesia
 * Time: 2014-04-06 13:33:57
 *
 * ZOJ 3767
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
int main(){
	int t;
	int n,m;
	cin >> t;
	while (t--){
		scanf("%d%d", &n, &m);
		int sum = 0,cnt;
		for (int i = 0; i < n; i ++){
			scanf("%d",&cnt);
			sum += cnt;
		}
		if (sum > m) puts("Warning");
		else puts("Safe");
	}
	return 0;
}

Posted on Edited on

使用pppoeconf命令拨号

第一次用的时候：

启用有线连接：

1
sudo ifconfig eth0 up

在终端中输入:

1
sudo pppoeconf

之后在需要的时候启动ADSL连接，可以在终端中输入：

1
sudo pon dsl-provider

断开ADSL连接，可以在终端中输入：

1
sudo poff dsl-provider

如果你发现连接正常工作，尝试手动去调整你之前ADSL连接的配置。

需要查看日志，可以在终端中输入：

1
plog

获得接口信息，可以在终端中输入：

1
ifconfig ppp0

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info

Posted on Edited on

dp[i][0]表示从上面落到i的左边的横向最短距离

dp[i][0]表示从上面落到i的右边的横向最短距离

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
#define MAX_VAL 999999999
#define maxn 1010
struct Node{
	int l,r,h;
}p[maxn];
int dp[maxn][3];//dp[i][0] 表示从上面落到i的左边的最短

bool cmp(Node a,Node b){
	if (a.h == b.h) return a.l < b.l;
	return a.h > b.h;
}

int main(int argc, char const *argv[])
{
	int MAX,x,n,y,T,ans;
	scanf("%d", &T);
	while (T--){
		memset(dp, 0, sizeof(dp));
		ans = MAX_VAL;
		scanf("%d%d%d%d", &n, &x, &y, &MAX);
		for (int i = 1; i <= n; i ++){
			scanf("%d%d%d", &p[i].l, &p[i].r, &p[i].h);
			dp[i][0] = dp[i][1] = MAX_VAL;
		}
		p[0].h = y;
		p[0].l = p[0].r = x;
		sort(p, p + n + 1, cmp);
		p[n + 1].h = 0;
		p[n + 1].l = -20000;
		p[n + 1].r =  20000;
		dp[0][0] = 0;dp[0][1] = 0;
		for (int i = 0; i <= n ; ++i){
			//bleft和bright用于标记从第i块木板左右两端下落是否找到了下一个落脚点
			bool bl = true, br = true;
			for (int j = i + 1; j <= 1 + n; j ++){
				if (!bl && !br || p[i].h - p[j].h > MAX) break;
				if (p[j].l <= p[i].l && p[j].r >= p[i].l && p[i].h != p[j].h && bl){
					bl = false;
					if (j == n + 1){
						ans = min(ans,dp[i][0]);
					}else {
						dp[j][0] = min(p[i].l - p[j].l + dp[i][0],dp[j][0]);
						dp[j][1] = min(p[j].r - p[i].l + dp[i][0],dp[j][1]);
					}
				}
				if (p[i].r <= p[j].r && p[i].r >= p[j].l && p[i].h != p[j].h && br){
					br = false;
					if (j == n + 1){
						ans = min(ans,dp[i][1]);
					}else {
						dp[j][0] = min(p[i].r - p[j].l + dp[i][1],dp[j][0]);
						dp[j][1] = min(p[j].r - p[i].r + dp[i][1],dp[j][1]);
					}
				}
			}
		}
		printf("%dn", ans + y);
	}
	return 0;
}