P2670 [NOIP2015 普及组] 扫雷游戏
#include <cstdio>
char mine[105][105];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%s", mine[i]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mine[i][j] == '*') continue; // 跳过这一次循环
int cnt = 0;
for (int k = 0; k < 8; k++) {
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < m && mine[x][y] == '*')
cnt++;
}
mine[i][j] = '0' + cnt;
}
}
for (int i = 0; i < n; i++) printf("%s\n", mine[i]);
return 0;
}
P1042 [NOIP2003 普及组] 乒乓球
#include <cstdio>
#include <string>
using namespace std;
int score[2] = {11, 21};
int main() {
char ch = getchar();
string record;
while (ch != 'E') {
if (ch == 'W' || ch == 'L') record += ch;
ch = getchar();
}
int len = record.length();
for (int i = 0; i < 2; i++) {
int x = 0, y = 0;
for (int j = 0; j < len; j++) {
if (record[j] == 'W') x++;
else y++;
if (max(x, y) >= score[i] && abs(x - y) >= 2) {
printf("%d:%d\n", x, y);
x = y = 0;
}
}
printf("%d:%d\n", x, y);
if (i == 0) printf("\n");
}
return 0;
}
P1563 [NOIP2016 提高组] 玩具谜题
#include <cstdio>
struct Toy {
int d;
char name[15];
};
Toy t[100005];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d%s", &t[i].d, t[i].name);
}
int cur = 0;
for (int i = 0; i < m; i++) {
int a, s;
scanf("%d%d", &a, &s);
int flag = -1;
if (a + t[cur].d == 1) flag = 1;
cur = (cur + n + flag * s) % n;
}
printf("%s\n", t[cur].name);
return 0;
}
%n 的结果取值范围为 0 ~ n-1，在程序中要注意和原始下标的对应关系
P4924 [1007] 魔法少女小Scarlet
#include <cstdio>
using namespace std;
int a[505][505], tmp[505][505];
int n;
void print() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
printf("%d ", a[i][j]);
printf("\n");
}
}
void rotate(int x, int y, int len, int d) {
for (int i = 0; i < len; ++i)
for (int j = 0; j < len; ++j)
if (d == 1) tmp[x + i][y + j] = a[x + j][y + len - i - 1];
else tmp[x + i][y + j] = a[x + len - j - 1][y + i];
for (int i = 0; i < len; ++i)
for (int j = 0; j < len; ++j)
a[x + i][y + j] = tmp[x + i][y + j];
}
int main()
{
int m;
scanf("%d%d", &n, &m);
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
a[i][j] = ++cnt;
for (int i = 0; i < m; i++) {
int x, y, r, z;
scanf("%d%d%d%d", &x, &y, &r, &z);
rotate(x - r, y - r, 2 * r + 1, z);
}
print();
return 0;
}
P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布
#include <cstdio>
int res[5][5] = {
{0, -1, 1, 1, -1},
{1, 0, -1, 1, -1},
{-1, 1, 0, -1, 1},
{-1, -1, 1, 0, 1},
{1, 1, -1, -1, 0}};
int a[205], b[205];
int main()
{
int n, na, nb;
scanf("%d%d%d", &n, &na, &nb);
for (int i = 0; i < na; ++i) scanf("%d", &a[i]);
for (int i = 0; i < nb; ++i) scanf("%d", &b[i]);
int sa = 0, sb = 0;
for (int i = 0; i < n; ++i) {
int r = res[a[i % na]][b[i % nb]];
if (r == 1) ++sa;
else if (r == -1) ++sb;
}
printf("%d %d\n", sa, sb);
return 0;
}
P1067 [NOIP2009 普及组] 多项式输出
#include <cstdio>
#include <cmath>
using namespace std;
int a[105];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i <= n; ++i) scanf("%d", &a[i]);
int bg = 0;
while (bg <= n && a[bg] == 0) ++bg;
if (bg == n + 1) printf("0");
for (int i = bg; i <= n; ++i) {
if (a[i] == 0) continue;
if (i != bg) {
if (a[i] > 0) printf("+");
else printf("-");
} else if (a[i] < 0) printf("-");
if (abs(a[i]) != 1 || i == n) printf("%d", abs(a[i]));
if (i < n) {
if (i == n - 1) printf("x");
else printf("x^%d", n - i);
}
}
return 0;
}
P1098 [NOIP2007 提高组] 字符串的展开
#include <iostream>
#include <string>
using namespace std;
string ans, s;
int p1, p2, p3;
bool is_lower(char ch) {
return ch >= 'a' && ch <= 'z';
}
bool is_digit(char ch) {
return ch >= '0' && ch <= '9';
}
bool can_expand(char l, char r) {
if (is_lower(l) && is_lower(r) && l < r) return true;
if (is_digit(l) && is_digit(r) && l < r) return true;
return false;
}
string expand(int l, int r) {
string ret;
if (p1 == 3) {
for (char ch = s[l] + 1; ch < s[r]; ++ch)
for (int i = 0; i < p2; ++i) ret += '*';
} else if (is_digit(s[l]) || p1 == 1) {
if (p3 == 2) {
for (char ch = s[r] - 1; ch > s[l]; --ch)
for (int i = 0; i < p2; ++i) ret += ch;
} else {
for (char ch = s[l] + 1; ch < s[r]; ++ch)
for (int i = 0; i < p2; ++i) ret += ch;
}
} else if (p1 == 2) {
if (p3 == 2) {
for (char ch = s[r] - 1; ch > s[l]; --ch)
for (int i = 0; i < p2; ++i) ret += char(ch - 32);
} else {
for (char ch = s[l] + 1; ch < s[r]; ++ch)
for (int i = 0; i < p2; ++i) ret += char(ch - 32);
}
}
return ret;
}
int main()
{
cin >> p1 >> p2 >> p3 >> s;
int bg = 0;
int len = s.length();
int cur = -1;
while (bg < len && cur < len) {
cur = s.find('-', cur + 1);
if (cur == -1) {
ans += s.substr(bg);
break;
}
if (cur != 0 && cur + 1 != s.length()) {
if (can_expand(s[cur - 1], s[cur + 1])) {
ans += s.substr(bg, cur - bg);
ans += expand(cur - 1, cur + 1);
ans += s[cur + 1];
bg = cur + 2;
++cur;
}
}
}
cout << ans << endl;
return 0;
}
P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two
#include <cstdio>
char s[15][15];
// 0 1 2 3
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool vis[15][15][4][15][15][4];
bool valid(int x) {
return x>=0 && x<=9;
}
void one_minute(int &x, int &y, int &d) {
int new_x = x + dx[d], new_y = y + dy[d];
if (valid(new_x) && valid(new_y) && s[new_x][new_y]!='*') {
x = new_x; y = new_y;
} else {
d = (d + 1) % 4;
}
}
int main()
{
int fx, fy, fd, cx, cy, cd;
for (int i = 0; i < 10; i++) scanf("%s", s[i]);
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++) {
if (s[i][j] == 'C') {
cx = i; cy = j;
}
if (s[i][j] == 'F') {
fx = i; fy = j;
}
}
fd = cd = 0;
int ans = 0;
vis[fx][fy][fd][cx][cy][cd]=true;
while (fx!=cx || fy!=cy) { // !(fx==cx && fy==cy)
one_minute(fx, fy, fd);
one_minute(cx, cy, cd);
if (vis[fx][fy][fd][cx][cy][cd]) {
ans=0; break;
}
vis[fx][fy][fd][cx][cy][cd]=true;
ans++;
}
printf("%d\n", ans);
return 0;
}
P1065 [NOIP2006 提高组] 作业调度方案
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int seq[405]; // 输入的安排顺序
int machine_id[25][25]; // machine_id[x][y]: 工件x的第y道工序在哪台机器上加工
int time_cost[25][25]; // time_cost[x][y]: 工件x的第y道工序的加工时间
int finish[25]; // finish[x]: 工件x已完成多少道工序
int end_time[25]; // end_time[x]: 工件x上一道工序的完成时刻
// machine[x][y][0/1]: 机器x的第y个空闲时间段
// [0/1]分别为空闲开始时间和结束时间 初始时统一为 0 ~ 无穷
int machine[25][25][2];
int sz[25]; // sz[x]代表机器x上有多少个空闲时间段
int main() {
int m, n;
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
machine[i][1][1] = INF;
sz[i] = 1;
}
for (int i = 0; i < m * n; i++) scanf("%d", &seq[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &machine_id[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &time_cost[i][j]);
int ans = 0;
for (int i = 0; i < m * n; i++) {
int cur = seq[i]; // 当前对哪个工件进行加工
int order = finish[cur] + 1; // 该工件即将进行第几道工序
int start_time = end_time[cur]; // 该工件在机器上至少要从哪个时刻开始可以加工
int mch_id = machine_id[cur][order]; // 该工件当前这道工序放在哪台机器上加工
int cost = time_cost[cur][order]; // 该工件当前这道工序所需的加工时间
// 寻找机器上符合要求的第一个可以用来加工的空闲时间段
for (int j = 1; j <= sz[mch_id]; j++) {
// 该空闲时间段为[bg,ed]
int bg = machine[mch_id][j][0], ed = machine[mch_id][j][1];
if (ed >= start_time) { // 至少要在start_time时刻之后
int available_time = ed - max(start_time, bg);
if (available_time >= cost) { // 该空闲时间段可用来加工
int occupy_bg = max(start_time, bg);
int occupy_ed = occupy_bg + cost;
// 这次加工将占用[occupy_bg,occupy_ed]这个时间段
// 分类讨论：
// 1.[bg,ed]全用完；
// 2.[bg,ed]的前半段或后半段被占用；
// 3.[bg,ed]被拆成两段空闲时间
if (ed - bg == occupy_ed - occupy_bg) {
// 此时这个空闲时间段将在数组中消失，进行数组元素删除
for (int k = j; k < sz[mch_id]; k++) {
machine[mch_id][k][0] = machine[mch_id][k + 1][0];
machine[mch_id][k][1] = machine[mch_id][k + 1][1];
}
sz[mch_id]--;
} else if (occupy_bg == bg) {
// 此时直接更新这个空闲时间段的开始时间即可
machine[mch_id][j][0] = occupy_ed;
} else if (occupy_ed == ed) {
// 此时直接更新这个空闲时间段的终止时间即可
machine[mch_id][j][1] = occupy_bg;
} else {
// 此时[bg,ed]被拆成[bg,occupy_bg]和[occupy_ed,ed]
machine[mch_id][j][1] = occupy_bg;
// 将[occupy_ed+1,ed]插入到数组中
for (int k = sz[mch_id]; k > j; k--) {
machine[mch_id][k + 1][0] = machine[mch_id][k][0];
machine[mch_id][k + 1][1] = machine[mch_id][k][1];
}
machine[mch_id][j + 1][0] = occupy_ed;
machine[mch_id][j + 1][1] = ed;
sz[mch_id]++;
}
finish[cur]++;
end_time[cur] = occupy_ed;
if (occupy_ed > ans) ans = occupy_ed;
break;
}
}
}
}
printf("%d\n", ans);
return 0;
}