最近脑子抽的厉害，东学一点，西补一点，着急+浮躁+粗心=爆零啊。
A - Question 1
SPOJ - SERGRID
这就道BFS模板题，没啥好说的，清醒后一发过。。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define LL long long
#define MAXN 505
#define CLR(x) memset(x, 0, sizeof(x))
char ss[MAXN][MAXN];
int land[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int n, m;
struct node{
int x, y;
int step;
};
int BFS()
{
queue <node> q;
node now;
now.x = 0; now.y = 0; now.step = 0;
q.push(now);
memset(vis, false, sizeof(vis));
vis[now.x][now.y] = true;
while(!q.empty())
{
now = q.front();
q.pop();
if (now.x == n-1 && now.y == m-1) return now.step;
int r, c;
for (int i = 0; i < 4; i++)
{
int cnt = land[now.x][now.y];/*可以跳跃的步数*/
r = now.x + cnt*dx[i];
c = now.y + cnt*dy[i];
if (r<n && r>=0 && c<m && c>=0 && !vis[r][c])
{
vis[r][c] = true;
node next;
next.x = r;
next.y = c;
next.step = now.step + 1;
q.push(next);
}
}
}
return -1;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
{
getchar();
for (int j = 0; j < m; j++)
{
scanf("%c", &ss[i][j]);
land[i][j] = ss[i][j] - '0'; //注意数字是连续输入的，要处理一下
}
}
int res = BFS();
printf("%d", res);
return 0;
}
B - Question 2
SPOJ - IAPCR2F **
这题。。并查集模板题，当时脑抽，写了一个while，没跳出死循环，然后累加数据的时候出错了，队友讲题的时候，还大言不惭说找不出错。。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define MAXN 1005
#define CLR(x) memset(x, 0, sizeof(x))
int pre[MAXN], a[MAXN], res[MAXN];
int cmp(int x, int y)
{
return x > y;
}
int Find(int x)
{
return pre[x]==x ? pre[x] : Find(pre[x]);
}
void Uion(int x, int y)
{
int xx = Find(x), yy = Find(y);
if (xx != yy)
{
pre[xx] = yy;
//a[yy] += a[xx]; 为啥不在这累加，手推一下就知道了
}
}
int main()
{
int t;
scanf("%d", &t);
int k = 1;
while(t--)
{
CLR(res);
CLR(a);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
pre[i] = i;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int u, v;
for (int i = 0; i < m; i++)
{
scanf("%d %d", &u, &v);
Uion(u, v);
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
if (pre[i]==i) cnt++; //原本写了一个while。。无明确跳出，死循环，第一题就一直TLE，心态炸啊
res[Find(i)] += a[i];
}
sort(res+1, res+n+1, cmp);
if (n==1)
{
printf("Case %d: 1\n", k++);
printf("%d\n", a[1]);
continue;
}
printf("Case %d: %d\n", k++, cnt);
for (int i = cnt; i >= 1; i--)
{
if (i == 1) printf("%d\n", res[1]);
else printf("%d ", res[i]);
}
}
return 0;
}
C - Question 3
SPOJ - VECTAR1
这题是个矩阵异或。。。记住vis矩阵要开对大小，不然一定会wa
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define LL long long
#define MAXN 1005
#define mod 1000000007
#define CLR(x) memset(x, 0, sizeof(x))
int vis[1000000]; //笔者直接开了1000^2
LL maxx;
void BuildMart(int n, int m)
{
CLR(vis);
//CLR(mat);
maxx = -1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
vis[i^j]++;
maxx = max(maxx, (LL)i^j);
}
//return maxx;
}
LL JieCeng(LL n)
{
LL ans = 1;
for (int i = 2; i <= n; i++)
{
ans *= i;
ans %= mod;
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n, m;
scanf("%d%d", &n, &m);
BuildMart(n, m);
LL res = 1;
for (int i = 0; i <= maxx; i++)
{
if (vis[i])
{
res *= JieCeng((LL)vis[i]);
res %= mod;
}
}
printf("%lld\n", res);
}
}
D - Question 4
CodeForces - 779B
最简单的一题，笔者理解错意思了，WA在test20，8发，心态崩了，后来在code forces上测数据才明白搞错意思了
笔者 想复杂了，以为要各种分类讨论。。。最近脑子抽。。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define MAXN 1005
#define CLR(x) memset(x, 0, sizeof(x))
char str[15];
int x;
int main()
{
scanf("%s %d", str, &x);
int len = strlen(str);
int zero = 0, fz = 0;
for (int i = len-1; i >= 0; i--)
{
if (str[i] == '0') zero++;
else fz++;
if (zero == x) break;
}
if (zero == x) printf("%d", fz); //如果可以整除，输出需要去除的数的个数
else printf("%d", len-1); //否则直接输出长度减一
return 0;
}
E - Question 5
CodeForces - 779C
E题其实就是贪心。。。然后，补题的时候理解错题意，数值一直不对，要不就是wa，后来的纸上推了一遍，发现。。。又想多了。。。或者说忘了自己排过序了。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define mod 1000000007
#define CLR(x) memset(x, 0, sizeof(x))
int n ,m ;
struct node{
int now, next;
int d;
}prc[200005];
int cmp(node x, node y)
{
//if (x.d == y.d) return x.now < y.now;
return x.d > y.d;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d", &prc[i].now);
int cnt = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &prc[i].next);
prc[i].d = prc[i].next - prc[i].now;
if (prc[i].d > 0) cnt++; //这周买合算
}
sort(prc, prc+n, cmp); //由这周买最合算到最不合算
LL ans = 0;
for (int i = 0; i < n; i++)
{
if (prc[i].d > 0)//排过序，前头的肯定是最合算
{
ans += prc[i].now;
m--;
}
else//本周买最合算的买完后
{
if (m > 0) //本周还需买m-cnt个商品
{
ans += prc[i].now;
m--;
}
else //下周买
ans += prc[i].next;
}
}
printf("%I64d", ans);
}
最近真的太急功近利了，该缓缓，好好补缺补漏，打好基础才能走的更远！！
