题目整理1

hihocoder offers8的3道题，都非常有意思。
做了2道，有一道有思路没时间补了。

• A题

** tag**: 数论
题目链接：http://hihocoder.com/contest/offers8/problem/1
解法：

1. 等价于要满足关系式 (D*i) mod L <= L-F, i为任意自然数，
2. 就是要找(D*i) mod L 中最大的那个数。
3. 若f(y)为 max({x|0<=x<y, gcd(x,y)==1}), 最大的那个数就为
   gcd(D,L)*f(L/gcd(D,L));
4. 求f(y) 可以从大到小枚举

代码:

#include<cstdio>
int gcd(int a, int b) {
    return b?gcd(b,a%b):a;
}
bool check(int l, int f, int d) {
    if(f>l) return false;
    if(d==0) return false;
    int gd = gcd(l, d);
    l/=gd;
    int i;
    for(i=l-1; i>=0; --i) {
        if(gcd(i,l)==1) break;
    }
    if(gd*i+f>gd*l) return false;
    return true;
}
int main() {
    int t; scanf("%d", &t);
    while(t--) {
        int l, f, d;
        scanf("%d%d%d", &l, &f, &d);
        if(check(l,f,d)) puts("YES");
        else puts("NO");
    }
    return 0;
}

• B题

** tag**: 并查集， 连通块
题目链接:http://hihocoder.com/contest/offers8/problem/2
解法

1. 求连通块可以用并查集
2. 由于列数为第一关键字，行数为第二关键字,标号要从要从左到有，再从上到下标，合并时设集合中标号最小的为代表元
3. 统计的时候可以用map,因为map为平衡二叉树，遍历的时候自然有序
   4,输出矩阵的时候，不在当前连通块，但在当前矩阵的不能输出
   5 注意left, right, up, down, 中存在不能做变量名的，不然会WA.

代码

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 1<<10;
int dbg = 0;
int id[MAXN][MAXN];
bool mat[MAXN][MAXN];
int fa[MAXN*MAXN];
int n, m;
int getfa(int x) {
    if(x==fa[x]) return x;
    return fa[x]=getfa(fa[x]);
}
struct  Node{
    int u, d, l, r, key;
    Node() {
        u = n;
        d = 1;
        l = m;
        r = 1;
    }
    void print() {
            printf("%d %d\n", d-u+1, r-l+1);
            for(int i=u; i<=d; ++i) {
                for(int j=l; j<=r; ++j) {
                    if(getfa(id[i][j])==key) putchar('1');
                        else putchar('0');
                }
                puts("");
            }
    }
};
map<int,Node> mp;
int step[][2] = {{-1,0},{0,-1}};

void merge(int u, int v) {
    u=getfa(u);
    v=getfa(v);
    fa[u] = fa[v]=min(u,v);
}
int main() {
    scanf("%d%d", &n, &m);
    char s[MAXN];
    for(int i=1; i<=n; ++i) {
        scanf("%s", s+1);
        for(int j=1; j<=m; ++j)
            mat[i][j] = (s[j]=='1');
    }
    int sz=0;
    for(int j=1; j<=m; ++j)
        for(int i=1; i<=n; ++i) {
            id[i][j] = ++sz;
            fa[sz] = sz;
        }
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(mat[i][j])
            {
                for(int k=0; k<2; ++k) {
                    int x =i+step[k][0];
                    int y =j+step[k][1];
                    if(mat[x][y]) merge(id[i][j], id[x][y]);
                }
            }
    mp.clear();
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(mat[i][j]) {
                int key=getfa(id[i][j]);
                Node& now = mp[key];
                now.key=key;
                now.u = min(now.u, i);
                now.d = max(now.d, i);
                now.l = min(now.l, j);
                now.r = max(now.r, j);
            }
    map<int,Node>::iterator it=mp.begin();
    for(;it!=mp.end(); ++it)
        (it->second).print();
    return 0;
}

• C题

tag: dp， 可以不用树状数组
题目链接:http://hihocoder.com/contest/offers8/problem/3
解法

1. n*n的方法很简单，现在针对它进行该进。
2. 假设dp[i]代表前i个数的方法数
3. 其实几乎前面所有的方法都可以选，但前缀和等于sum[i]的不能所以，统计前缀和为sum[i]的方法个数，设为cnt[sum[i]]
4. sum[i]可能为负，可以离散化
5. dp方程

    total = cnt[sum[0]] = 1;
    for(int i=1; i<=n; ++i) {
        dp[i] = (total-cnt[sum[i]])%MOD;
        cnt[sum[i]] = (cnt[sum[i]]+dp[i])%MOD;
        total = (total+dp[i])%MOD;
    }

6. 用树状数组求total非常不好。