Chengrui's Blog

0%

发表于 分类于 ， Disqus：

给出一个区间，问其中哪个数因子最多。对每个数进行唯一分解，然后求出素因子乘积即为因子个数。

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
#include <cstdio>
using namespace std;
const int maxn = 34000;
int prime[maxn],p;
bool np[maxn]={true,true};
void pre() {
    for(int i = 2; i < maxn; ++i) {
        if(!np[i]) prime[p++] = i;
        for(int j = 0; j < p && i * prime[j] < maxn; ++j) {
            np[i * prime[j]] = true;
            if(!(i % prime[j])) break;
        }
    }
    return;
}
int solve(int n) {
    int cur = 1;
    for(int i = 0; i < p; ++i) {
        int cnt=1;
        if(n % prime[i] == 0) {
            while(n % prime[i] == 0 && n)
                n /= prime[i], ++cnt;
            cur *= cnt;
        }
    }
    return cur;
}
int main() {
    pre();
    int t; scanf("%d", &t);
    while(t--) {
        int l, r; scanf("%d%d", &l, &r);
        int max_n = 0, ans = l;
        for(int i = l; i <= r; ++i) {
            int k=solve(i);
            if(k > max_n) max_n = k,ans =i;
        }
        printf("Between %d and %d, %d has a maximum of %d divisors.\n", l, r, ans, max_n);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

将序列储存两遍，用数组代替环，然后枚举起点，每次都把当前数交换过来，即可得到答案。

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

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int a[maxn], b[maxn];

int main() {
    int n;
    while(~scanf("%d", &n) && n) {
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[n + i] = a[i];
        int ans = inf, cur = 0;
        for(int i = 1; i <= n; ++i) {
            memcpy(b, a, sizeof(a));
            cur = 0;
            for(int j = 1; j <= n && cur < ans; ++j) {
                int k = i + j - 1;
                if(b[k] != j) {
                    ++cur;
                    int pos = k + 1;
                    while(pos < i + n) {
                        if(b[pos] == j) {swap(b[k], b[pos]); break;}
                        ++pos;
                    }
                }
            }
            ans = min(ans, cur);
            memcpy(b, a, sizeof(a));
            cur = 0;
            for(int j = n; j >= 1 && cur < ans; --j) {
                int k = i + n - j;
                if(b[k] != j) {
                    ++cur;
                    int pos = k + 1;
                    while(pos < i + n){
                        if(b[pos] == j) {swap(b[k], b[pos]); break;}
                        ++pos;
                    }
                }
            }
            ans = min(ans, cur);
        }
        printf("%d\n", ans);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

书上给了公式，照着敲的。

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 <cstdio>
using namespace std;
const int maxn = 1010;
const int mod = 10056;
int c[maxn][maxn];
int f[maxn];
void pre() {
    for(int i = 0; i < maxn; ++i) c[i][0] = 1;
    for(int i = 1; i < maxn; ++i)
        for(int j = 1;j <= i; ++j)
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
    f[0] = 1;
    for(int i = 1; i < maxn; ++i)
        for(int j = 0; j <= i; ++j)
            f[i] += f[i-j] * c[i][j], f[i] %= mod;
}
int main() {
    pre();
    int t, n, tt=0;scanf("%d",&t);
    while(t--){
        scanf("%d", &n);
        printf("Case %d: %d\n", ++tt, f[n]);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

在挑战程序设计竞赛上做过类似的，二分答案判断是否合理。

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
#include <cstdio>
#include <stack>
using namespace std;
typedef long long LL;

const int maxn = 510;
LL a[maxn];
stack <LL> p[maxn];
int m,k;

bool ok(LL ans) {
    int pos=m,t=k;
    while(t--){
        LL cur=ans;
        while(cur>a[pos]){
            cur-=a[pos--];
            if(!pos) return true;
        }
    }
    return !pos;
}

int main() {
    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &m, &k);
        LL l = 0, r = 6000000000;
        for(int i = 1; i <= m; ++i) scanf("%lld", &a[i]), l = max(l, a[i]);
        LL  mid = (l + r) / 2;
        while(l < r) {
            mid = l + (r - l) / 2;
            if(ok(mid)){
                if(!ok(mid - 1)){--mid; break;}
                else r = mid + 1;
            }
            else l = mid;
        }
        if(ok(l)) mid = l;
        int pos = m;
        for(int i = k; i > 0; --i){
            while(!p[i].empty()) p[i].pop();
            LL t = mid;
            while(t >= a[pos] && pos) {
                t-=a[pos], p[i].push(a[pos--]);
                if(pos < i) break;
            }
        }
        for(int i = 1; i <= k; ++i) {
            while(!p[i].empty()){
                printf("%lld", p[i].top()), p[i].pop();
                if(!p[i].empty()) printf(" ");
            }
            printf(i == k ? "\n" : " / ");
        }
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

简单题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q;
int main() {
    int n, ans, k;
    while(~scanf("%d", &n) && n) {
        while(!q.empty()) q.pop();
        ans = 0;
        while(n--) scanf("%d", &k), q.push(k);
        while(q.size() > 1) {
            int a,b;
            a = q.top(), q.pop(), b = q.top(), q.pop();
            q.push(a + b);
            ans += a + b;
        }
        printf("%d\n", ans);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

首先对枚举所有可能的时间间隔，然后暴力每个工作之后间隔多久进行下一个，当当前时间加上最短间隔乘剩余个数大于最优解时回溯。

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

const int maxn = 25;
int n, a[5], dt[maxn], ans, cnt;

bool ok(int *p, int k) {
    for(int i = 0; i < 5; ++i)
        if(a[i] &(p[i] >> k)) return false;
    return true;
}

void dfs(int *p, int d, int sum) {
    if(sum + dt[0] * (10 - d) >= ans) return;
    if(d == 10) {ans = min(ans, sum); return; }
    for(int i = 0; i < cnt; ++i) {
        if(ok(p, dt[i])) {
            int p2[5];
            for(int j = 0; j < 5; ++j)
                p2[j] =(p[j] >> dt[i]) | a[j];
            dfs(p2, d+1, sum + dt[i]);
        }
    }
    return;
}

int main() {
    while(~scanf("%d", &n) && n) {
        memset(a, 0, sizeof(a));
        memset(dt, 0, sizeof(dt));
        for(int i = 0; i < 5; ++i) {
            char s[maxn]; scanf("%s", s);
            for(int j = 0; j < n; ++j)
                if(s[j] == 'X') a[i] |=(1 << j);
        }
        cnt = 0;
        for(int i = 1; i <= n; ++i)
            if(ok(a, i)) dt[cnt++]=i;
        ans = 10 * n;
        dfs(a, 1, n);
        printf("%d\n", ans);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

书上给出了详细的思路，通过DFS判断，若连通上下边界就不能通过，若连通左右就更新解。

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int n;
bool vis[maxn];
double left, right;
struct node {
    double x,y,r;
    bool inter(node a) {
        double dx = x - a.x, dy = y - a.y;
        return dx * dx + dy * dy - (r + a.r) * (r + a.r) <= 0;
    }
} a[maxn];
bool dfs(int cur) {
    vis[cur] = true;
    if (a[cur].y - a[cur].r <= 0) return false;
    if (a[cur].x - a[cur].r <= 0)
        left = min(left, a[cur].y - sqrt(a[cur].r * a[cur].r - a[cur].x * a[cur].x));
    if (a[cur].x + a[cur].r >= 1000)
        right = min(right, a[cur].y - sqrt(a[cur].r * a[cur].r - (1000 - a[cur].x) * (1000 - a[cur].x)));
    for (int i = 0; i < n; ++i) {
        if (vis[i]) continue;
        if (a[cur].inter(a[i]))
            if(!dfs(i)) return false;
    }
    return true;
}
void solve() {
    left = right = 1000;
    for (int i = 0; i < n; ++i) {
        if(!vis[i] && a[i].y + a[i].r >= 1000)
            if(!dfs(i)) {
                puts("IMPOSSIBLE");
                return;
            }
    }
    printf("0.00 %.2lf 1000.00 %.2lf\n", left, right);
}
int main() {
    while (~scanf("%d", &n)) {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r);
        solve();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出 n ∗ m 个单元格，可能是数据也可能是引用。若能计算出所有值，输出表格，否则输出不能算出的单元格。
对每个进行DFS，若出现环则无法计算。

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
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<cctype>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=210;
int n,m,num;
int a[maxn];
bool loop,ok[maxn],vis[maxn];
string s[maxn];
struct node{
    int id,sign;
    node(int id=0,int sign=0):id(id),sign(sign){}
};
vector<node> ex[maxn];
int dfs(int cur){
    if(!ok[cur]){
        loop=true;
        return 0;
    }
    if(ex[cur].empty()) return a[cur];
    if(vis[cur]){
        ok[cur]=false;
        loop=true;
        return 0;
    }
    vis[cur]=true;
    for(int i=0;i<ex[cur].size();++i){
        node& k=ex[cur][i];
        if(ok[k.id]) a[cur]+=k.sign*dfs(k.id);
        if(!ok[k.id]){
            ok[cur]=false;
            loop=true;
        }
    }
    ex[cur].clear();
    return a[cur];
}
int main(){
    while(cin>>n>>m&&n&&m){
        loop=false;
        memset(a,0,sizeof(a));
        memset(ok,1,sizeof(ok));
        memset(vis,0,sizeof(vis));
        int num=n*m;
        for(int i=0;i<num;++i){
            cin>>s[i];
            string k=s[i];
            vector<int> sign;
            if(k[0]=='-') sign.push_back(-1);
            else sign.push_back(1);
            for(int j=0;j<k.length();++j){
                if(k[j]=='-') sign.push_back(-1),k[j]=' ';
                else if(k[j]=='+') sign.push_back(1),k[j]=' ';
            }
            stringstream ss(k);
            int pos=0;
            ex[i].clear();
            while(ss>>k){
                if(isdigit(k[0])){
                    istringstream tmp(k);
                    int cur;
                    tmp>>cur;
                    a[i]+=cur*sign[pos++];
                }
                else ex[i].push_back(node((k[0]-'A')*m+(k[1]-'0'),sign[pos++]));
            }
        }
        for(int i=0;i<num;++i) dfs(i);
        if(loop){
            for(int i=0;i<num;++i)
                if(!ok[i]) printf("%c%d: %s\n",i/m+'A',i%m,s[i].c_str());
        }
        else{
            putchar(' ');
            for(int i=0;i<m;++i) printf("%6d",i);
            puts("");
            for(int i=0;i<n;++i){
                printf("%c",i+'A');
                for(int j=0;j<m;++j) printf("%6d",a[i*m+j]);
                puts("");
            }
        }
        puts("");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出 n 个车的范围，输出在 n ＊ n 的棋盘上可行的摆法。
车的行和列是相互独立的，所以问题就简化成了两个一维的区间覆盖问题。
用优先队列维护区间起点最小的车放在编号最小的位置。

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
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=5010;
struct node{
    int l,r,id;
    node(int l=0,int r=0,int id=0):l(l),r(r),id(id){}
    bool operator < (const node& x) const {
        return l==x.l?r>x.r:l>x.l;
    }
};
priority_queue<node> x,y;
int pos[2][maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        while(!x.empty()) x.pop();
        while(!y.empty()) y.pop();
        for(int i=1;i<=n;++i){
            int l1,l2,r1,r2;
            scanf("%d%d%d%d",&l1,&l2,&r1,&r2);
            x.push(node(l1,r1,i)),y.push(node(l2,r2,i));
        }
        bool flag=true;
        for(int i=1;i<=n;++i){
            node t;
            while((t=x.top()).l<i) x.pop(),t.l=i,x.push(t);
            if(x.top().l>i){flag=false;break;}
            if(x.top().l==i&&x.top().r>=i) pos[0][x.top().id]=i,x.pop();
            else {flag=false;break;}
            while((t=y.top()).l<i) y.pop(),t.l=i,y.push(t);
            if(y.top().l==i&&y.top().r>=i) pos[1][y.top().id]=i,y.pop();
            else {flag=false;break;}
        }
        if(flag) for(int i=1;i<=n;++i) printf("%d %d\n",pos[0][i],pos[1][i]);
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一个木棒和 m 个切点，每次切割需要花费等于当前木棒长度的费用。问最小花费。
对整个区间DP然后枚举区间的所有间断点。
转移方程为 d [ i ] [ j ] = m i n ( d [ i ] [ k ] + d [ k ] [ j ] ) 。

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
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=55;
const int inf=0x3f3f3f3f;
int a[maxn],d[maxn][maxn];
int dp(int l,int r){
    int& k=d[l][r];
    if(l>=r-1) return k=0;
    if(k!=inf) return k;
    for(int i=l+1;i<r;++i)
        k=min(k,dp(l,i)+dp(i,r)+a[r]-a[l]);
    return k;
}
int main(){
    int l,n;
    while(~scanf("%d",&l)&&l){
        memset(d,0x3f,sizeof(d));
        scanf("%d",&n);
        a[0]=0,a[n+1]=l;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        printf("The minimum cutting is %d.\n",dp(0,n+1));
    }
    return 0;
}

网上搜到的优化版本：

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

using namespace std;

inline int Rint()
{
    int c;
    while(!isdigit(c = getchar()));
    int t = c ^ 48;
    while(isdigit(c = getchar()))
        t = (t << 1) + (t << 3) + (c ^ 48);
    return t;
}

const int N = 55;
int d[N][N], s[N][N], x[N];

int main()
{
    for (int l; scanf("%d", &l) == 1 && l; )
    {
        int n = Rint();
        for (int i = 1; i <= n; ++i) x[i] = Rint();
        x[++n] = l;
        for (int i = 0; i < n; ++i) d[i][i+1] = 0, s[i][i+1] = i;
        for (int i = n - 2; i >= 0; --i)
            for (int j = i + 2; j <= n; ++j)
            {
                int val = 2000000, p;
                int st = max(s[i][j-1], i + 1), dt = min(s[i + 1][j], j - 1);
                for (int k = st; k <= dt; ++k)
                {
                    int t = d[i][k] + d[k][j];
                    if (t < val) val = t, p = k;
                }
                d[i][j] = val + x[j] - x[i], s[i][j] = p;
            }
        printf("The minimum cutting is %d.\n", d[0][n]);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **