SGU – hahaschool

SGU 195 New Year Bonus Grant

July 30, 20152015-07-30hahaschoolLeave a comment

题意

某厂采用一种奇怪的方式发奖金，给出一个上下级关系树，大BOSS是1号根节点，别的员工都有自己的上司。对于每个员工，它有三种选择，要么接受上级下发的奖金，要么给所有下级发奖金，要么啥都不做（只有傻子才会这样，所以你可以当成没这种选择），大BOSS一定发奖金。只要一个员工选择收奖金，他就得到1000块。

现在要你设计一种方案，使得所有人收到的奖金的总数额最大。

思路

树DP解法

对于每一个节点，都有两种状态：选择收奖金，选择收奖金。

对于选择收奖金的节点的儿子节点，一定不可以选择收奖金。

对于选择发奖金的节点的儿子节点，可以选择收他的奖金，也可以选择发奖金。

这样就可以建立dp数组dp[a][0/1]，a是节点对应的编号，0/1表示该节点选择收／发奖金的状态。利用DFS下潜到叶子节点之后，就可以开始树DP了。

状态转移的方程可以参考dfs()方法。

输出路径的话，只要记录下每一次的决策，DP结束之后反查就可以搞定。

贪心解法

引用自JHC23的Blog。

自底而顶遍历，如果自己的上级没有接受奖金（那么就能够把钱给发自己了），而自己也从不增接受奖金则可以获得奖金，同时标记自己和上级。这样下去就可以得到可得到最大奖金。

代码

树DP解法：

//
//  SGU195.cpp
//  playground
//
//  Created by Adam Chang on 2015/07/29.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct nodeType{
    vector<int> to;
    int select;
} vertex[500005];

void addEdge(int from,int to){
    vertex[from].to.push_back(to);
}

int dp[500005][2];
void dfs(int cur){
    nodeType &currNode = vertex[cur];
    for (int i = 0; i < currNode.to.size(); i++) {
        dfs(currNode.to[i]);
    }
    for (int i = 0; i < currNode.to.size(); i++) {
        if (dp[cur][0]+dp[currNode.to[i]][0]+1>= max(dp[cur][1]+dp[currNode.to[i]][1],dp[cur][1]+dp[currNode.to[i]][0])) {
            currNode.select = currNode.to[i];
        }
        dp[cur][1] = max(dp[cur][0]+dp[currNode.to[i]][0]+1, max(dp[cur][1]+dp[currNode.to[i]][1],dp[cur][1]+dp[currNode.to[i]][0]));
        dp[cur][0] = max(dp[cur][0]+dp[currNode.to[i]][1],dp[cur][0]+dp[currNode.to[i]][0]);
    }
}

vector<int> ans;
void dfs_getans(int cur){
    nodeType &currNode = vertex[cur];
    if (dp[cur][0] >= dp[cur][1]) {
        for (int i = 0; i < currNode.to.size(); i++) {
            dfs_getans(currNode.to[i]);
        }
    }else{
        if (currNode.select) {
            ans.push_back(currNode.select);
        }
        for (int i = 0; i < currNode.to.size(); i++) {
            dfs_getans(currNode.to[i]);
        }
    }
}

int main(){
    int n = 0;
    scanf(" %d",&n);
    for (int i = 1; i <= n; i++) {
        vertex[i].to.clear();
        vertex[i].select = 0;
        dp[i][0] = dp[i][1] = 0;
    }
    ans.clear();
    for (int i = 2; i <= n; i++) {
        int boss = 0;
        scanf(" %d",&boss);
        addEdge(boss,i);
    }
    dfs(1);
    dfs_getans(1);
    sort(ans.begin(), ans.end());
    cerr << dp[1][0] << " " << dp[1][1] << endl;
    printf("%d\n",(int)ans.size()*1000);
    if (ans.size()) {
        for (int i = 0; i < (int)ans.size()-1; i++) {
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[ans.size()-1]);
    }
    return 0;
}

// SGU195.cpp

// playground

// Created by Adam Chang on 2015/07/29.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct nodeType{

vector<int> to;

int select;

} vertex[500005];

void addEdge(int from,int to){

vertex[from].to.push_back(to);

}

int dp[500005][2];

void dfs(int cur){

nodeType &currNode = vertex[cur];

for (int i = 0; i < currNode.to.size(); i++) {

dfs(currNode.to[i]);

}

for (int i = 0; i < currNode.to.size(); i++) {

if (dp[cur][0]+dp[currNode.to[i]][0]+1>= max(dp[cur][1]+dp[currNode.to[i]][1],dp[cur][1]+dp[currNode.to[i]][0])) {

currNode.select = currNode.to[i];

}

dp[cur][1] = max(dp[cur][0]+dp[currNode.to[i]][0]+1, max(dp[cur][1]+dp[currNode.to[i]][1],dp[cur][1]+dp[currNode.to[i]][0]));

dp[cur][0] = max(dp[cur][0]+dp[currNode.to[i]][1],dp[cur][0]+dp[currNode.to[i]][0]);

}

vector<int> ans;

void dfs_getans(int cur){

nodeType &currNode = vertex[cur];

if (dp[cur][0] >= dp[cur][1]) {

for (int i = 0; i < currNode.to.size(); i++) {

dfs_getans(currNode.to[i]);

}

}else{

if (currNode.select) {

ans.push_back(currNode.select);

}

for (int i = 0; i < currNode.to.size(); i++) {

dfs_getans(currNode.to[i]);

}

int main(){

int n = 0;

scanf(" %d",&n);

for (int i = 1; i <= n; i++) {

vertex[i].to.clear();

vertex[i].select = 0;

dp[i][0] = dp[i][1] = 0;

}

ans.clear();

for (int i = 2; i <= n; i++) {

int boss = 0;

scanf(" %d",&boss);

addEdge(boss,i);

}

dfs(1);

dfs_getans(1);

sort(ans.begin(), ans.end());

cerr << dp[1][0] << " " << dp[1][1] << endl;

printf("%d\n",(int)ans.size()*1000);

if (ans.size()) {

for (int i = 0; i < (int)ans.size()-1; i++) {

printf("%d ",ans[i]);

}

printf("%d\n",ans[ans.size()-1]);

}

return 0;

}

SGU 126 Boxes

April 07, 20152015-04-07hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/126，翻译版。

思路

我是手写一些找规律，所以我也没办法细讲。

http://www.nocow.cn/index.php/Sgu/126详细题解，说是一个数论题，因为我是找规律所以代码肯定是写不严的，如果你需要严格证明请移步那边。

代码

#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main(){
    long long a = 0,b = 0,sum = 0;
    cin >> a >> b;
    sum = a+b;
    if(a == 0 || b == 0){
        cout << 0 << endl;
    }
    if(sum%2){
        cout << -1 << endl;
        return 0;
    }
    int res = 0;
    long long now = min(a,b);
    while(now != sum/2){
        if(res > 10000){
            cout << -1 << endl;
            return 0;
        }
        res++;
        now *= 2;
        now = min(now,sum-now);
    }
    cout << res+1 << endl;
    return 0;
}

#include <iostream>

#include <cstdlib>

#include <algorithm>

using namespace std;

int main(){

long long a = 0,b = 0,sum = 0;

cin >> a >> b;

sum = a+b;

if(a == 0 || b == 0){

cout << 0 << endl;

}

if(sum%2){

cout << -1 << endl;

return 0;

}

int res = 0;

long long now = min(a,b);

while(now != sum/2){

if(res > 10000){

cout << -1 << endl;

return 0;

}

res++;

now *= 2;

now = min(now,sum-now);

}

cout << res+1 << endl;

return 0;

}

SGU 101 Domino

April 07, 20152015-04-07hahaschoolLeave a comment

题意

给你一堆骨牌，每张骨牌正反两面各有一个0～6范围内的数字，你要做的是确定一种骨牌的排列方式和骨牌的正反似的相邻的两个骨牌的面数字一样。

思路

这种链接多个物体，物体之间通过公共部分链接，这种题是可以转换成图论题做的。那么这个题应该怎么转换？
我们建立0～6这7个节点，每张骨牌就可以看作是链接骨牌上两个数的边，我们要做的就是找到一个路径使得我们可以“一笔”走过所有的边，其实这个叫欧拉通路。
关于欧拉通路，欧拉回路的更多细节，可以参看http://haha.school/guanyuoulahuiluheoulalujing/。
找出欧拉回路的方法就是DFS，但是和以往不同的是我们把处理工作放在下一层返回之后做。同时本题还需要判断欧拉回路是否存在，如果不存在的话要输出无解。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

vector<pair<int, int> > ljb[7];//first to second id
int n = 0;

bool vis[105];
int res[105];
int now = 0;
void dfs(int currNode){
    for (int i = 0; i < ljb[currNode].size(); i++) {
        if(!vis[abs(ljb[currNode][i].second)]){
            vis[abs(ljb[currNode][i].second)] = true;
            dfs(ljb[currNode][i].first);
            now++;
            res[now] = ljb[currNode][i].second;
        }
    }
}

int main(){
    for(int i = 0;i <= 6;i++)
    ljb[i].clear();
    scanf(" %d",&n);
    int oddpnt = 0;
    for(int i = 1;i <= n;i++){
        int a = 0,b = 0;
        scanf(" %d %d",&a,&b);
        oddpnt = a;
        ljb[a].push_back(make_pair(b,i));
        ljb[b].push_back(make_pair(a,-i));
    }
    int oddcnt = 0,evencnt = 0;
    for (int i = 0; i <= 6; i++) {
            if (ljb[i].size()%2) {
                oddcnt++;
                oddpnt = i;
            }else{
                evencnt++;
            }
    }
    if (evencnt == 7 || oddcnt == 2) {
        memset(vis,0,sizeof(vis));
        memset(res, 0, sizeof(res));
        now = 0;
        dfs(oddpnt);
        if (now != n) {
            printf("No solution\n");
        }else{
            for (int i = n; i >= 1; i--) {
                if (res[i] > 0) {
                    printf("%d +\n",res[i]);
                }else{
                    printf("%d -\n",abs(res[i]));
                }
            }

        }
    }else{
        printf("No solution\n");
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

vector<pair<int, int> > ljb[7];//first to second id

int n = 0;

bool vis[105];

int res[105];

int now = 0;

void dfs(int currNode){

for (int i = 0; i < ljb[currNode].size(); i++) {

if(!vis[abs(ljb[currNode][i].second)]){

vis[abs(ljb[currNode][i].second)] = true;

dfs(ljb[currNode][i].first);

now++;

res[now] = ljb[currNode][i].second;

}

int main(){

for(int i = 0;i <= 6;i++)

ljb[i].clear();

scanf(" %d",&n);

int oddpnt = 0;

for(int i = 1;i <= n;i++){

int a = 0,b = 0;

scanf(" %d %d",&a,&b);

oddpnt = a;

ljb[a].push_back(make_pair(b,i));

ljb[b].push_back(make_pair(a,-i));

}

int oddcnt = 0,evencnt = 0;

for (int i = 0; i <= 6; i++) {

if (ljb[i].size()%2) {

oddcnt++;

oddpnt = i;

}else{

evencnt++;

}

if (evencnt == 7 || oddcnt == 2) {

memset(vis,0,sizeof(vis));

memset(res, 0, sizeof(res));

now = 0;

dfs(oddpnt);

if (now != n) {

printf("No solution\n");

}else{

for (int i = n; i >= 1; i--) {

if (res[i] > 0) {

printf("%d +\n",res[i]);

}else{

printf("%d -\n",abs(res[i]));

}

}else{

printf("No solution\n");

}

return 0;

}

SGU 123 The sum

April 07, 20152015-04-07hahaschoolLeave a comment

题意

打出斐波那契数列前41项。

思路

没啥好说的，入门经典题。对于新手来说，容易跪在直接求斐波那契的题的原因一般是没有采用记忆化的方法（存住之前的每一个值），而是每一次都重新推一遍，这样就超时了。要么就是没有注意到int范围弄爆了，或者把longlong弄爆了（这个时候应该是java大法好）。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

long long fib[43];
long long sum[43];

int main(){
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= 41; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    sum[0] = 0;
    for (int i = 1; i <= 41; i++) {
        sum[i] = sum[i-1]+fib[i];
    }
    int toQuery = 0;
    scanf(" %d",&toQuery);
    printf("%lld\n",sum[toQuery]);

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

long long fib[43];

long long sum[43];

int main(){

fib[1] = 1;

fib[2] = 1;

for (int i = 3; i <= 41; i++) {

fib[i] = fib[i-1] + fib[i-2];

}

sum[0] = 0;

for (int i = 1; i <= 41; i++) {

sum[i] = sum[i-1]+fib[i];

}

int toQuery = 0;

scanf(" %d",&toQuery);

printf("%lld\n",sum[toQuery]);

return 0;

}

SGU 108 Self-numbers 2

April 06, 20152015-04-06hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/108，翻译版，这里不再多说。

思路

这个题刚到手其实都是会写的，但是一般交上去会发现爆内存，原因就是我们用来判定self number的数组开太大了，要想减少空间复杂度只能从这个数组入手，那么我们真的需要那么大的数组么？显然是不用的，通过本题的数据范围可以发现N最大为7位数，即使7位全是9，我们能够更新到的数组区域长度也仅为63个单位，所以我们把bool标记数组开个63长度就够了，开100那更是没问题，这个技巧就是所谓的“滚动数组”。
滚动数组的操作方法有几点：1.通过求余来确定位置 2.使用完当前位置后，要给它初始化为没有使用过的样子以便以后的元素正常使用。
仅仅使用滚动数组还不足以完成这个题，还要注意输出答案的方式，因为数组在滚动，所以你不可能在完成判定之后再输出结果，而是应该边滚动判定，边记录，最后把记录的输出去。
本题有几个坑点：首先你要把输出的目标索引排个序，否则如果数据是乱序的基本都会跪，其次要注意请求的索引中是有重复的，可能一个索引被请求了多次。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

bool isself[100];
vector<pair<int, int> > goal;
int container[5005];

bool cmp(pair<int, int> a,pair<int, int> b){
    return a.first < b.first;
}

int main(){
    int n = 0,k = 0;
    scanf(" %d %d",&n,&k);
    goal.clear();
    for (int i = 1; i <= k; i++) {
        int tmp = 0;
        scanf(" %d",&tmp);
        goal.push_back(make_pair(tmp, i));
    }
    sort(goal.begin(), goal.end(),cmp);
    memset(isself, true, sizeof(isself));
    memset(container, 0, sizeof(container));
    int cnt = 0;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        if (isself[i%64]) {
            cnt++;
            while (cnt == goal[cur].first) {
                container[goal[cur].second] = i;
                cur++;
            }
        }
        int tmp = i,sum = i;
        while (tmp != 0) {
            sum += tmp%10;
            tmp /= 10;
        }
        isself[sum%64] = false;
        isself[i%64] = true;
    }
    printf("%d\n",cnt);
    for (int i = 1;i < k; i++) {
        printf("%d ",container[i]);
    }
    printf("%d\n",container[k]);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

bool isself[100];

vector<pair<int, int> > goal;

int container[5005];

bool cmp(pair<int, int> a,pair<int, int> b){

return a.first < b.first;

}

int main(){

int n = 0,k = 0;

scanf(" %d %d",&n,&k);

goal.clear();

for (int i = 1; i <= k; i++) {

int tmp = 0;

scanf(" %d",&tmp);

goal.push_back(make_pair(tmp, i));

}

sort(goal.begin(), goal.end(),cmp);

memset(isself, true, sizeof(isself));

memset(container, 0, sizeof(container));

int cnt = 0;

int cur = 0;

for (int i = 1; i <= n; i++) {

if (isself[i%64]) {

cnt++;

while (cnt == goal[cur].first) {

container[goal[cur].second] = i;

cur++;

}

int tmp = i,sum = i;

while (tmp != 0) {

sum += tmp%10;

tmp /= 10;

}

isself[sum%64] = false;

isself[i%64] = true;

}

printf("%d\n",cnt);

for (int i = 1;i < k; i++) {

printf("%d ",container[i]);

}

printf("%d\n",container[k]);

return 0;

}

SGU 107 987654321 problem

April 01, 20152015-04-01hahaschoolLeave a comment

题意

给你n，让你输出n位数中平方后尾数是987654321的数的个数。

思路

一个数，只考虑最后i位，那么这个数平方之后的最后i位和这个数的最后i位平方后的最后i位相同，所以我们只要考虑1～9位数中谁的平方最后9位是987654321就可以了，本地打个表，发现只有8个数符合要求，接下来，对于10位数，我们就有98=72种组合对于11位数就是908=720种组合，这样我们就发现了，超过10位数的话，就在73后面补上n-10个零就行了，这样大数时也搞定了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int main(){
    int a = 0;
    scanf("%d",&a);
    if (a <= 8) {
        printf("0n");
    }else if(a == 9){
        printf("8n");
    }else{
        printf("72");
        for (int i = 10; i < a; i++) {
            printf("0");
        }
        printf("n");
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int main(){

int a = 0;

scanf("%d",&a);

if (a <= 8) {

printf("0n");

}else if(a == 9){

printf("8n");

}else{

printf("72");

for (int i = 10; i < a; i++) {

printf("0");

}

printf("n");

}

return 0;

}

SGU 104 Little shop of flowers

April 01, 20152015-04-01hahaschoolLeave a comment

题意

插花，给你若干花瓶和若干把花，花瓶个数大于等于花的把数，每把花都不一样，要求你让每把花都插进花瓶里面，花瓶不一定每个都要用，但是你必须保证插完之后花的排列顺序和原来给出的一样。然后给了你一个花插进花瓶之后产生的美学价值对照表，要你设计一种方案使得这样插花所达到的美学价值最大。

思路

典型的背包问题，我们设计一个二维dp数组dp[i][j]，令i表示当前已经考虑到第几把花，令j表示对于当前这把花我们插入到前j个花瓶，那么我们一把一把花处理，对于每把花枚举其插入每个花瓶的结果，同时要继承上一把花插入到这个花瓶之前的全部状态中最优的那个（因为要保证有序）。最后枚举dp[n][j]的j，找到最佳状态就好了。
接下来要考虑怎么输出最优方案，其实不难想，我们可以给dp数组加上一维或者单开一个pre[i][j]数组，与dp数组平行工作，保存当前状态的前置状态，最后顺着最佳状态不断回溯输出就搞定了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int aes[105][105];
int dp[105][105][2]; // 0 is value 1 is pre

int main(){
    int f = 0,v = 0;
    scanf(" %d %d",&f,&v);
    memset(aes, 0, sizeof(aes));
    for (int i = 1; i <= f; i++) {
        for (int j = 1; j <= v; j++) {
            scanf(" %d",&aes[i][j]);
        }
    }
    memset(dp, 0xf3f3, sizeof(dp));
    for (int i = 1; i <= v; i++) {
        dp[1][i][0] = aes[1][i];
        dp[1][i][1] = 0;
    }
    for (int i = 1; i <= f; i++) {
        for (int j = 2; j <= v; j++) {
            for (int k = 1;k < j; k++) {
                if (dp[i][j][0] < dp[i-1][k][0] + aes[i][j]) {
                    dp[i][j][0] = dp[i-1][k][0] + aes[i][j];
                    dp[i][j][1] = k;
                }
            }
        }
    }
    int maxn = 0xf3f3f3f3,maxi = 0;
    for (int i = 1; i <= v; i++) {
        if (dp[f][i][0] > maxn) {
            maxn = dp[f][i][0];
            maxi = i;
        }
    }
    stack<int> curstk;
    int cur = maxi;
    while (f) {
        curstk.push(cur);
        cur = dp[f--][cur][1];
    }
    printf("%dn",maxn);
    while (curstk.size() > 1) {
        printf("%d ",curstk.top());
        curstk.pop();
    }
    printf("%dn",curstk.top());
    curstk.pop();

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int aes[105][105];

int dp[105][105][2]; // 0 is value 1 is pre

int main(){

int f = 0,v = 0;

scanf(" %d %d",&f,&v);

memset(aes, 0, sizeof(aes));

for (int i = 1; i <= f; i++) {

for (int j = 1; j <= v; j++) {

scanf(" %d",&aes[i][j]);

}

memset(dp, 0xf3f3, sizeof(dp));

for (int i = 1; i <= v; i++) {

dp[1][i][0] = aes[1][i];

dp[1][i][1] = 0;

}

for (int i = 1; i <= f; i++) {

for (int j = 2; j <= v; j++) {

for (int k = 1;k < j; k++) {

if (dp[i][j][0] < dp[i-1][k][0] + aes[i][j]) {

dp[i][j][0] = dp[i-1][k][0] + aes[i][j];

dp[i][j][1] = k;

}

int maxn = 0xf3f3f3f3,maxi = 0;

for (int i = 1; i <= v; i++) {

if (dp[f][i][0] > maxn) {

maxn = dp[f][i][0];

maxi = i;

}

stack<int> curstk;

int cur = maxi;

while (f) {

curstk.push(cur);

cur = dp[f--][cur][1];

}

printf("%dn",maxn);

while (curstk.size() > 1) {

printf("%d ",curstk.top());

curstk.pop();

}

printf("%dn",curstk.top());

curstk.pop();

return 0;

}

SGU 103 Traffic Lights

March 22, 20152015-03-22hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/103
翻译版，这里不重复劳动了

思路

这个题的可怕之处不是有多难想，而是虽然基本模型很简单就是图上最短路，但是这回有许多许多的限制条件。
正确地计算当前灯的状态是这个题最大的难点，我采用的方法是（其实我写跪了，李大神给我捞上来的）：首先把到这个路口已经消耗的时间减去题目给的初始时间，我叫他有效时间，接下来把这个有效时间模上两种颜色的灯持续时间之和，剩下的时间是对灯的状态真正有影响的时间，接下来分别脑内模拟一下站在这个路灯时如果是紫色最后会怎么变，如果是蓝色会怎么变，然后基本就可以写出这个时间和最终颜色的关系了，还可以得到最终这个颜色还能再持续多长时间，这两条非常重要，一定要搞对。
接下来的难点就是计算从当前点移动到下一个点之前等待两点灯的颜色同步的时间，算这个就要依赖于上面的两个值：当前颜色和当前颜色还剩多长时间，假设我们要从A点移动到B，已经走了tim时间，那么我们就要分别计算A点和B点在tim时的这两个数据，然后如果AB在tim时颜色正好相等，那么无需等待直接通行，所以等待时间为0，如果颜色不同呢？只要看A和B哪个剩余的时间短，这个就是等待时间了。要是剩余的时间又一样？那就要脑内模拟一下了，然后发现我们可以再比较A的下一颜色和B的下一颜色谁的持续时间短，等待时间就是剩余时间＋最短的持续时间。如果下一个颜色还一样，那就比较下下个颜色。要是还一样？对不起，hehe了，走别的吧～（所以说这个题很sxbk)
接下来是最段路部分，我们把权值设定为走到这个点要花多少时间，从当前点走到下一个点时，下一个点的可能值就是(当前点已用时间+等待两个点的灯同步的时间+路上消耗的时间)，以此为基准进行松弛操作。

接下来上代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int str = 0,ter = 0;
int n = 0,m = 0;

struct edgeType{
    int to;
    int cost;
    edgeType(){
        to = 0;
        cost = 0;
    }
    edgeType(int ito,int icost){
        to = ito;
        cost = icost;
    }
};

struct vertexType{
    char color;
    int init;
    int blue;
    int purple;
    int pre;//for backtracking
    int dis;
    vector<edgeType> edge;
    vertexType(){
        color = 0;
        init = 0;
        blue = 0;
        purple = 0;
        pre = 0;
        dis = 0x3f3f3f3f;
        edge.clear();
    }
} vertex[305];

char getColor(int timepast,int a){
    vertexType &av = vertex[a];
    int atime = (timepast % (av.blue+av.purple)) - av.init;
    if (av.color == 'P') {
        if (atime < 0) {
            return 'P';
        }else if(atime < av.blue){
            return 'B';
        }else{
            return 'P';
        }
    }else{
        if (atime < 0) {
            return 'B';
        }else if(atime < av.purple){
            return 'P';
        }else{
            return 'B';
        }
    }
}
char getTime(int timepast,int a){
    vertexType &av = vertex[a];
    int atime = (timepast %(av.blue+av.purple)) - av.init;
    if (av.color == 'P') {
        if (atime < 0) {
            return -atime;
        }else if(atime < av.blue){
            return av.blue-atime;
        }else{
            return av.blue+av.purple-atime;
        }
    }else{
        if (atime < 0) {
            return -atime;
        }else if(atime < av.purple){
            return av.purple-atime;
        }else{
            return av.blue+av.purple-atime;
        }
    }
}

int waitTime(int a,int b){
    //from a to b
    vertexType &av = vertex[a];
    vertexType &bv = vertex[b];
    int atime = getTime(av.dis, a);
    int btime = getTime(av.dis, b);
    char acolor = getColor(av.dis,a);
    char bcolor = getColor(av.dis,b);
    if (acolor == bcolor) {
        return 0;
    }
    if (abs(atime - btime)) {
        return min(atime,btime);
    }else if(acolor == 'P'){
        if (abs(av.blue-bv.purple)) {
            return atime+min(av.blue,bv.purple);
        }else if(abs(av.purple-bv.blue)){
            return atime+av.blue+min(av.purple,bv.blue);
        }else{
            return -1;
        }
    }else if(acolor == 'B'){
        if (abs(av.purple-bv.blue)) {
            return atime+min(av.purple,bv.blue);
        }else if(abs(av.blue-bv.purple)){
            return atime+av.purple+min(av.blue,bv.purple);
        }else{
            return -1;
        }
    }else{
        return -1;
    }
}

struct cmp{
    bool operator () (int a,int b){
        return vertex[a].dis > vertex[b].dis;
    }
};

void dijkstra(){
    vertex[str].dis = 0;
    priority_queue<int,vector<int>,cmp> q;
    q.push(str);
    bool vis[305];
    memset(vis, 0, sizeof(vis));
    while (!q.empty()) {
        int nown = q.top();
        q.pop();
        vis[nown] = true;
        vertexType &nowv = vertex[nown];
        for (int i = 0; i < nowv.edge.size(); i++) {
            int nextn = nowv.edge[i].to;
            vertexType &nextv = vertex[nextn];
            if (vis[nextn]) {
                continue;
            }
            int wait = waitTime(nown,nextn);
            if (wait == -1) {
                continue;
            }
            if (wait + nowv.dis + nowv.edge[i].cost < nextv.dis) {
                //relax
                nextv.dis = wait + nowv.dis + nowv.edge[i].cost;
                nextv.pre = nown;
                q.push(nextn);
            }
        }
    }

}



int main(){
    scanf(" %d %d %d %d",&str,&ter,&n,&m);
    for (int i = 1; i <= n; i++) {
        scanf(" %c %d %d %d",&vertex[i].color,&vertex[i].init,&vertex[i].blue,&vertex[i].purple);
    }
    for (int i = 1; i <= m; i++) {
        int a = 0,b = 0,c = 0;
        scanf(" %d %d %d",&a,&b,&c);
        vertex[a].edge.push_back(edgeType(b,c));
        vertex[b].edge.push_back(edgeType(a,c));
    }
    dijkstra();
    if (vertex[ter].dis == 0x3f3f3f3f) {
        printf("0\n");
        return 0;
    }
    printf("%d\n",vertex[ter].dis);
    stack<int> path;
    int curr = ter;
    while (curr) {
        path.push(curr);
        curr = vertex[curr].pre;
    }
    while (path.size()>1) {
        printf("%d ",path.top());
        path.pop();
    }
    printf("%d\n",path.top());
    path.pop();

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int str = 0,ter = 0;

int n = 0,m = 0;

struct edgeType{

int to;

int cost;

edgeType(){

to = 0;

cost = 0;

}

edgeType(int ito,int icost){

to = ito;

cost = icost;

}

};

struct vertexType{

char color;

int init;

int blue;

int purple;

int pre;//for backtracking

int dis;

vector<edgeType> edge;

vertexType(){

color = 0;

init = 0;

blue = 0;

purple = 0;

pre = 0;

dis = 0x3f3f3f3f;

edge.clear();

}

} vertex[305];

char getColor(int timepast,int a){

vertexType &av = vertex[a];

int atime = (timepast % (av.blue+av.purple)) - av.init;

if (av.color == 'P') {

if (atime < 0) {

return 'P';

}else if(atime < av.blue){

return 'B';

}else{

return 'P';

}

}else{

if (atime < 0) {

return 'B';

}else if(atime < av.purple){

return 'P';

}else{

return 'B';

}

char getTime(int timepast,int a){

vertexType &av = vertex[a];

int atime = (timepast %(av.blue+av.purple)) - av.init;

if (av.color == 'P') {

if (atime < 0) {

return -atime;

}else if(atime < av.blue){

return av.blue-atime;

}else{

return av.blue+av.purple-atime;

}

}else{

if (atime < 0) {

return -atime;

}else if(atime < av.purple){

return av.purple-atime;

}else{

return av.blue+av.purple-atime;

}

int waitTime(int a,int b){

//from a to b

vertexType &av = vertex[a];

vertexType &bv = vertex[b];

int atime = getTime(av.dis, a);

int btime = getTime(av.dis, b);

char acolor = getColor(av.dis,a);

char bcolor = getColor(av.dis,b);

if (acolor == bcolor) {

return 0;

}

if (abs(atime - btime)) {

return min(atime,btime);

}else if(acolor == 'P'){

if (abs(av.blue-bv.purple)) {

return atime+min(av.blue,bv.purple);

}else if(abs(av.purple-bv.blue)){

return atime+av.blue+min(av.purple,bv.blue);

}else{

return -1;

}

}else if(acolor == 'B'){

if (abs(av.purple-bv.blue)) {

return atime+min(av.purple,bv.blue);

}else if(abs(av.blue-bv.purple)){

return atime+av.purple+min(av.blue,bv.purple);

}else{

return -1;

}

}else{

return -1;

}

struct cmp{

bool operator () (int a,int b){

return vertex[a].dis > vertex[b].dis;

}

};

void dijkstra(){

vertex[str].dis = 0;

priority_queue<int,vector<int>,cmp> q;

q.push(str);

bool vis[305];

memset(vis, 0, sizeof(vis));

while (!q.empty()) {

int nown = q.top();

q.pop();

vis[nown] = true;

vertexType &nowv = vertex[nown];

for (int i = 0; i < nowv.edge.size(); i++) {

int nextn = nowv.edge[i].to;

vertexType &nextv = vertex[nextn];

if (vis[nextn]) {

continue;

}

int wait = waitTime(nown,nextn);

if (wait == -1) {

continue;

}

if (wait + nowv.dis + nowv.edge[i].cost < nextv.dis) {

//relax

nextv.dis = wait + nowv.dis + nowv.edge[i].cost;

nextv.pre = nown;

q.push(nextn);

}

int main(){

scanf(" %d %d %d %d",&str,&ter,&n,&m);

for (int i = 1; i <= n; i++) {

scanf(" %c %d %d %d",&vertex[i].color,&vertex[i].init,&vertex[i].blue,&vertex[i].purple);

}

for (int i = 1; i <= m; i++) {

int a = 0,b = 0,c = 0;

scanf(" %d %d %d",&a,&b,&c);

vertex[a].edge.push_back(edgeType(b,c));

vertex[b].edge.push_back(edgeType(a,c));

}

dijkstra();

if (vertex[ter].dis == 0x3f3f3f3f) {

printf("0\n");

return 0;

}

printf("%d\n",vertex[ter].dis);

stack<int> path;

int curr = ter;

while (curr) {

path.push(curr);

curr = vertex[curr].pre;

}

while (path.size()>1) {

printf("%d ",path.top());

path.pop();

}

printf("%d\n",path.top());

path.pop();

return 0;

}

SGU 102 Coprimes

January 21, 20152015-01-21hahaschoolLeave a comment

#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 10005

vector<int> decomp(int n){
    vector<int> res;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            n /= i;
            i = 1;
        }
    }
    return res;
}


int main(){
    int toQuery = 0;
    while (cin >> toQuery) {
        vector<int> dec = decomp(toQuery);
        sort(dec.begin(), dec.end());
        dec.erase(unique(dec.begin(), dec.end()),dec.end());
        for (int i = 0; i < dec.size(); i++) {
            toQuery *= dec[i]-1;
            toQuery /= dec[i];
        }
        cout << toQuery << endl;
    }
}

#include <cmath>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <vector>

#include <queue>

using namespace std;

#define MAXN 10005

vector<int> decomp(int n){

vector<int> res;

for (int i = 2; i <= n; i++) {

if (n % i == 0) {

res.push_back(i);

n /= i;

i = 1;

}

return res;

}

int main(){

int toQuery = 0;

while (cin >> toQuery) {

vector<int> dec = decomp(toQuery);

sort(dec.begin(), dec.end());

dec.erase(unique(dec.begin(), dec.end()),dec.end());

for (int i = 0; i < dec.size(); i++) {

toQuery *= dec[i]-1;

toQuery /= dec[i];

}

cout << toQuery << endl;

}

这个题是欧拉函数：http://baike.baidu.com/view/107769.htm，正好就是这货的定义，说实话我都不知道欧拉函数是啥，打表又没意思了。。。

简单的说就是这个数挨个乘上(n-1)/n，n是不同的质因数。

贴一个求欧拉函数更好的姿势：

ll phi(ll n)
{
    ll m=(ll)sqrt(n+0.5),ans=n;
    for(ll i=2;i<=m;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

ll phi(ll n)

{

ll m=(ll)sqrt(n+0.5),ans=n;

for(ll i=2;i<=m;i++)

{

if(n%i==0)

{

ans=ans/i*(i-1);

while(n%i==0)n/=i;

}

if(n>1)ans=ans/n*(n-1);

return ans;

}

降幂公式 a^b %c= a^(b%phi(c)+phi(c)) %c （b>=phi(c)）

这个是意外收获，可以用到欧拉函数的地方。

SGU 105 Div3

January 20, 20152015-01-20hahaschoolLeave a comment

#include <iostream>

using namespace std;

int main(){
    unsigned int toQuery;
    while (cin >> toQuery) {
        int tmp = 0;
        if (toQuery % 3 == 2) tmp++;
        cout << 2*(toQuery/3)+tmp << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main(){

unsigned int toQuery;

while (cin >> toQuery) {

int tmp = 0;

if (toQuery % 3 == 2) tmp++;

cout << 2*(toQuery/3)+tmp << endl;

}

return 0;

}

如果每一位加合等于3的话，这个数也可以被3整除。

然后打个表找下循环节发现是XOOXOOXOO这样的，直接简单判定一下实现就好了。