hihocoder offers8的3道题，都非常有意思。
做了2道，有一道有思路没时间补了。
-
A题
** tag**: 数论
题目链接：http://hihocoder.com/contest/offers8/problem/1
解法：
- 等价于要满足关系式 (D*i) mod L <= L-F, i为任意自然数，
- 就是要找(D*i) mod L 中最大的那个数。
- 若f(y)为 max({x|0<=x<y, gcd(x,y)==1}), 最大的那个数就为
gcd(D,L)*f(L/gcd(D,L));- 求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
解法
- 求连通块可以用并查集
- 由于列数为第一关键字，行数为第二关键字,标号要从要从左到有，再从上到下标，合并时设集合中标号最小的为代表元
- 统计的时候可以用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
解法
- n*n的方法很简单，现在针对它进行该进。
- 假设dp[i]代表前i个数的方法数
- 其实几乎前面所有的方法都可以选，但前缀和等于sum[i]的不能所以，统计前缀和为sum[i]的方法个数，设为cnt[sum[i]]
- sum[i]可能为负，可以离散化
- 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;
}
- 用树状数组求total非常不好。
