分类目录归档：算法

洛谷 P1022 计算器的改良

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int ratio = 0, constant = 0;
#define IfLetter if (ch <= 'Z'&&ch >= 'A' || ch <= 'z'&&ch >= 'a')
#define IfNumber if (ch >= '0'&&ch <= '9' || ch=='+' || ch=='-')
int main() {
    char letter;
    char ch;
    int num = 0;
    bool flag = true;
    while ((ch = getchar()) != '\n') {
        IfNumber{ // number(maybe with variable)
            ungetc(ch, stdin);
            int re = scanf("%d", &num); //specially prepared for the testcase form like "-a"
            if (re == 0) {
                getchar();
                ratio -= (flag ? 1 : -1);
            }
            ch = getchar();
            IfLetter{
                ratio += num * (flag ? 1 : -1);
                letter = ch;
            }
            else {
                constant += num * (flag ? 1 : -1);
                ungetc(ch, stdin);
            }
            num = 0;
        }
        else IfLetter{ //pure variable without ratio
            letter = ch;
            ratio+=(flag ? 1 : -1);
        }
        else if (ch == '=') {
            flag = false;
        }
    }
    printf("%c=%.3lf", letter, -1.0*constant / ratio);
}

洛谷 P2114 [NOI2014]起床困难综合症

发表评论

参看题解：
https://www.luogu.org/blog/user17941/solution-p2114
https://www.luogu.org/blog/user25845/solution-p2114

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int n, m, t[100005];
string s[100005];
int zero = 0, one = 0x7fffffff;
int ans = 0;
void process(int & x) {
    for (int i = 1; i <= n; i++) {
        switch (s[i][0]) {
        case 'A':
            x &= t[i];
            break;
        case 'O':
            x |= t[i];
            break;
        case 'X':
            x ^= t[i];
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> s[i] >> t[i];
    process(zero);
    process(one);
    for (int i = 31; i >= 0; i--) {
        if (ans + (1 << i) > m)continue;
        if (!(zero&(1<<i))&&(one&(1 << i)))ans |= (1 << i);
    }
    process(ans);
    cout << ans;
}

Openjudge BJUTACM 181A:素数和

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int n, m;
bool isprime[10000005];
int prime[10000005];
vector<int> primeList;
inline void genPrime() {
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= 10000000; i++) {
        if (!isprime[i])continue;
        primeList.push_back(i);
        for (int j = 2 * i; j <= 10000000; j += i) {
            isprime[j] = false;
        }
    }
}
inline void putIn(int v) {
    for (int i = 0; i < primeList.size() && v >= primeList[i] && v != 1; i++) {
        if (v%primeList[i] == 0) {
            prime[primeList[i]]++;
            while (v%primeList[i] == 0)v /= primeList[i];
        }
        if (isprime[v]) {
            prime[v]++;
            break;
        }
    }
}
int main() {
    genPrime();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d", &v);
        putIn(v);
    }
    for (int i = 1; i <= 10000000; i++) {
        prime[i] += prime[i - 1];
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        if (r > 10000000)r = 10000000;
        if (l > 10000000)l = 10000000;
        printf("%d\n", prime[r] - prime[l - 1]);
    }
}

http://bjutacm.openjudge.cn/lianxi/181A/

洛谷 P1199 三国游戏

发表评论

https://www.luogu.org/blog/user23248/solution-p1199

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
int n,a[501][501],maxV;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>a[i][j];
            a[j][i]=a[i][j];   
        }
    }
    for(int i=1;i<=n;i++){
        sort(a[i]+1,a[i]+n+1);
        maxV=max(maxV,a[i][n-1]);
    }
    cout<<1<<endl<<maxV;
}

洛谷 P1373 小a和uim之大逃离

发表评论

自己博客上好像全是代码了，正经的题解还没多少。。。
代码还都是一堆看别人题解写出来的。
https://www.luogu.org/blog/yh1127/solution-p1373

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
#include<iostream>
#include<cstring>
#define MOD 1000000007
using namespace std;
int f[805][805][17][2],a[805][805];
int n,m,k,ans;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    k++;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        cin>>a[i][j];
        f[i][j][a[i][j]][0]=1;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int p=0;p<=k-1;p++){
        f[i][j][p][1]+=f[i][j-1][(p+a[i][j])%k][0];
        f[i][j][p][1]%=MOD;
        f[i][j][p][1]+=f[i-1][j][(p+a[i][j])%k][0];
        f[i][j][p][1]%=MOD;
        f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k)%k][1];
        f[i][j][p][0]%=MOD;
        f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)%k][1];
                f[i][j][p][0]%=MOD;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        ans+=f[i][j][0][1];
        ans%=MOD;
    }
    cout<<ans;
}

洛谷 P2279 [HNOI2003]消防局的设立

发表评论

看了下题解，用贪心写的。动规真心不会。贪心还凑和。
参见题解：https://waautomaton.blog.luogu.org/solution-p2279

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n;
vector<int> edges[1005];
int depth[1005],father[1005],grandfather[1005];
struct node{
    int i,dep;
    node(int ii,int depp){i=ii;dep=depp;}
    bool operator < (const node& n2) const{
        return dep<n2.dep;
    }
};
priority_queue<node> pq;
bool visited[1005];
void dfsRange2(int pos,int dep){
//为什么这里不能发现visited之后就return呢，是因为有可能一个点虽被visited，但其周围的点未被扩展完全，所以其实visited在这里面没有任何作用，如果把注释去掉是20分的。
    //if(visited[pos])return;
    visited[pos]=true;
    if(dep==2)return;
    for(int i=0;i<edges[pos].size();i++){
        //if(visited[edges[pos][i]])continue;
        dfsRange2(edges[pos][i],dep+1);
    }
}
void dfsAll(int pos,int f,int gf,int dep){
    if(visited[pos])return;
    visited[pos]=true;
    father[pos]=f;
    grandfather[pos]=gf;
    depth[pos]=dep;
    for(int i=0;i<edges[pos].size();i++){
        if(visited[edges[pos][i]])continue;
        dfsAll(edges[pos][i],pos,f,dep+1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=2;i<=n;i++){
        int v;
        cin>>v;
        edges[i].push_back(v);
        edges[v].push_back(i);
    }
    memset(visited,false,sizeof(visited));
    dfsAll(1,1,1,1);
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++)pq.push(node(i,depth[i]));
    int cnter=0;
    while(!pq.empty()){
        if(visited[pq.top().i]){
            pq.pop();
            continue;
        }
        node cur=pq.top();pq.pop();
        dfsRange2(grandfather[cur.i],0);
        cnter++;
    }
    cout<<cnter;
}

洛谷 P1220 关路灯

发表评论

我递推啥都不会写垃圾死了，一道对我来说用递推非常难以解决的、难以思考的DP题目被我用记忆化递归解决了，0ms，高兴死我啦！
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，代码写的那么长。。

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
#include<iostream>
#include<cstring>
using namespace std;
int n,c;
int pos[55],power[55];
int prefixPower[55];
int f[55][55][2];
inline int getEnergy(int l,int r){
    return prefixPower[n]-prefixPower[r]+prefixPower[l-1];
}
int dp(int l,int r,int d){
    if(f[l][r][d]!=-1)return f[l][r][d];
    if(l==1&&r==n)return f[l][r][d]=0;
    if(l==1&&r<n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1);
    if(l>1&&r==n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0);
    else return f[l][r][d]=min(getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0),getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1));
}
int main(){
    ios::sync_with_stdio(false);
    memset(f,-1,sizeof(f));
    cin>>n>>c;
    for(int i=1;i<=n;i++)cin>>pos[i]>>power[i];
    for(int i=1;i<=n;i++)prefixPower[i]=prefixPower[i-1]+power[i];
    cout<<min(dp(c,c,0),dp(c,c,1));
}

洛谷 P1290 欧几里德的游戏

发表评论

又是一道博弈论：题解：
https://www.luogu.org/blog/DJCreeper/p1290-ti-xie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;
void Stan(int,int);
void Ollie(int,int);
void Stan(int i,int j){
    if(i==j||i/j>=2)cout<<"Stan wins"<<endl;
    else Ollie(max(i-j,j),min(i-j,j));
}
void Ollie(int i,int j){
    if(i==j||i/j>=2)cout<<"Ollie wins"<<endl;
        else Stan(max(i-j,j),min(i-j,j));
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int v1,v2;
        cin>>v1>>v2;
        if(v1<v2)swap(v1,v2);
        Stan(v1,v2);
    }
}

洛谷 P1441 砝码称重

发表评论

先写了个两层搜索，后来又参考题解改了个搜索+动态规划。
题解：https://www.luogu.org/blog/yeyangrui/solution-p1441
60分搜索：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
bool mass[2005];
int weight[25];
bool visited[25];
void dfs(int pos,int num){
    if(pos==n+1)return;
    if(visited[pos]){
        dfs(pos+1,num);
        return;
    }
    mass[num+weight[pos]]=true;
    dfs(pos+1,num+weight[pos]);
    mass[num]=true;
    dfs(pos+1,num);
}
int getMassCounts(){
    memset(mass,false,sizeof(mass));
    dfs(1,0);
    int cnter=0;
    for(int i=1;i<=n*100;i++)if(mass[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

100分动规：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
int f[2005];
int weight[25];
bool visited[25];
int getMassCounts(){
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        for(int j=2000;j>=0;j--){
            if(j+weight[i]<=2000&&f[j]!=0)f[j+weight[i]]=1;
        }
    }
    int cnter=0;
    for(int i=1;i<=2000;i++)if(f[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

洛谷 P2320 [HNOI2006]鬼谷子的钱袋

发表评论

想不出来：参考题解：
https://www.luogu.org/blog/user50514/solution-p2320
https://www.luogu.org/blog/user26625/solution-p2320

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll ans,n,z[70];
int main(){
    cin>>n;
    while(n){
        z[++ans]=(n+1)/2;
        n/=2;
    }
    sort(z+1,z+ans+1);
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)cout<<z[i]<<" ";
}