哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛）(AK题解)
A-Race
思路：
按照题意模拟一下即可。
代码：
int v1, v2, t, s, l;
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
cin >> v1 >> v2 >> t >> s >> l;
int now1 = 0;
int now2 = 0;
int ghs = 0;
int id;
repd(i, 1, 10000)
{
if (ghs > 0)
{
ghs--;
} else
{
now1 += v1;
}
now2 += v2;
if (now1 >= l || now2 >= l) {
id = i;
break;
}
if (ghs == 0 && now1 - now2 >= t)
{
ghs = s;
}
}
if (now1 == now2 && now2 == l)
{
printf("Tie %d\n", id );
} else if (now1 > now2)
{
printf("Ming %d\n", id );
} else
{
printf("Hong %d\n", id );
}
return 0;
} B-Min Value
思路：
很老的一种题目了，将数组排序一下，然后对于每一个数，二分找下数组中
左右两边的下标，然后在这个长度不大于3的小区间里找到
使
的绝对值最小。
代码：
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int n;
pii a[maxn];
int b[maxn];
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
n = readint();
repd(i, 1, n)
{
a[i].fi = readint();
a[i].se = i;
}
sort(a + 1, a + 1 + n);
repd(i, 1, n)
{
b[i] = a[i].fi;
}
int ans1 = inf;
int ans2 = inf;
repd(i, 1, n)
{
int pos = lower_bound(b + 1, b + 1 + n, -b[i]) - b - 1;
repd(j, max(1, pos), min(n, pos + 3))
{
if (a[i].se == a[j].se)
continue;
int num = abs(b[i] + b[j]);
if (num < ans1)
{
ans1 = num;
ans2 = a[i].se + a[j].se;
} else if (num == ans1)
{
ans2 = min(ans2, a[i].se + a[j].se);
}
}
}
printf("%d %d\n", ans1, ans2 );
return 0;
}
C-Coronavirus
思路：
非常基础的BFS题目，先将地图中不能走的位置处理一下，然后bfs即可。
代码：
const int maxn = 110;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
const int M = maxn;
int n;
int m;
char s[maxn][maxn];
struct BFSer
{
const int dx[4] = { -1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
int Dis[M][M]; bool vis[M][M]; int Frx[M][M], Fry[M][M];
struct node {int x, y;} Q[M * M];
int l, r;
void bfs(int sx, int sy)
{
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)Dis[i][j] = 5e8;
Dis[sx][sy] = 0; vis[sx][sy] = true; Q[r++] = (node) {sx, sy};
while (l < r)
{
node t = Q[l++];
int x = t.x, y = t.y;
for (int d = 0; d < 4; d++)
{
int xx = x + dx[d], yy = y + dy[d];
if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy] || s[xx][yy] == '*')continue;
Dis[xx][yy] = Dis[x][y] + 1; vis[xx][yy] = true;
Frx[xx][yy] = x; Fry[xx][yy] = y;
Q[r++] = (node) {xx, yy};
}
}
}
} bfser;
int dx8[8] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy8[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
n = readint();
m = readint();
repd(i, 1, n)
{
scanf("%s", s[i] + 1);
}
int sx, sy, ex, ey;
repd(i, 1, n)
repd(j, 1, m)
{
if (s[i][j] == 'S')
{
sx = i;
sy = j;
} else if (s[i][j] == 'E')
{
ex = i;
ey = j;
}
}
std::vector<pii> v;
repd(i, 1, n)
{
repd(j, 1, m)
{
if (s[i][j] == '*')
{
v.pb(mp(i, j));
}
}
}
for (auto &X : v)
{
int i = X.fi;
int j = X.se;
repd(k, 0, 7)
{
s[i + dx8[k]][j + dy8[k]] = '*';
}
}
if (s[sx][sy] == 'S')
{
bfser.bfs(sx, sy);
if (bfser.Dis[ex][ey] > 1e8)
{
printf("Impossible\n");
} else
{
printf("%d\n", bfser.Dis[ex][ey]);
}
} else
{
printf("Impossible\n");
}
return 0;
} D-Array
思路：
这题是Codeforces Round #628 (Div. 2)- D 题的弱化版，
题解可以看：
https://www.cnblogs.com/qieqiemin/p/13163717.html
我交了2种写法，都过了，分别是直接分类讨论构造，还有二进制拆分，都贴上吧。
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
ll x, y;
while (~scanf("%lld %lld", &x, &y))
{
if (x > y)
{
printf("-1\n");
} else
{
if (x == y) {
if (x == 0)
printf("0\n");
else
{
printf("1\n");
// printf("%lld\n", x);
}
} else {
ll c = y - x;
if (c & 1)
{
printf("-1\n");
} else
{
ll z = c / 2;
// chu(z);
// chu(z & x);
if ((z & x) == 0)
{
printf("2\n");
//printf("%lld %lld\n", x + c / 2, c / 2 );
} else
{
printf("3\n");
//printf("%lld %lld %lld\n", x, c / 2, c / 2 );
}
}
}
}
}
return 0;
} #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int a[30];
int b[30];
int c[30];
void PRINF2(ll num, int k)
{
for (int i = k; i >= 0; i--)
{
cout << (bool)(num & (1ll << i));
}
cout << endl;
}
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
int x, y;
while (~scanf("%d %d", &x, &y))
{
// PRINF2(x, 20);
// PRINF2(y, 20);
if (x % 2 != y % 2)
{
printf("-1\n");
} else if (x > y)
{
printf("-1\n");
} else
{
int cnt1 = 0;
int cnt2 = 0;
while (x > 0)
{
a[cnt1++] = x % 2;
x /= 2;
}
while (y > 0)
{
b[cnt2++] = y % 2;
y /= 2;
}
int ans = 0;
for (int i = cnt2; i >= 0; --i)
{
c[i] += b[i];
int flag = 0;
if (b[i] == 1 && a[i] == 0)
{
if (c[i] % 2 == 1)
{
flag = 1;
}
} else if (b[i] == 0 && a[i] == 1)
{
if (c[i] % 2 == 0)
{
flag = 1;
}
} else if (b[i] == 1 && a[i] == 1)
{
if (c[i] % 2 == 0)
{
flag = 1;
}
} else
{
if (c[i] % 2 == 1)
{
flag = 1;
}
}
if (flag)
{
if (i == 0) {
ans = -1;
break;
}
int add = 0;
if (c[i] == 0)
{
for (int j = i + 1; j <= cnt2; ++j)
{
if (c[j] >= 2)
{
c[j] -= 2;
add = 1 << (j - i + 1);
break;
}
}
}
c[i] += add;
c[i]--;
c[i - 1] += 2;
}
}
if (ans == -1)
{
printf("%d\n", -1 );
} else
{
repd(i, 0, 29) {ans = max(ans, c[i]);}
ans %= 4;
printf("%d\n", ans );
}
}
// for (int i = 20; i >= 0; --i) {cout << c[i];}; cout << endl;
repd(i, 0, 29) {a[i] = b[i] = c[i] = 0;}
}
return 0;
} E-Prize
思路：
对于数字0~9，用bitset<805> 表示数字可以放在中奖号码的哪些位。
然后1~n遍历彩民的号码，
用bitset<805> pre代表上一个位置结束时能匹配到中奖号码的哪些位，
用bitset<805> b代表遍历到当前数字时能匹配到中奖号码的哪些位置。
如果,说明当前位置可以作为一个中奖号码的结束，
同时用数组代表以第
个数字为结束时，最多中奖多少次。
答案即为。
代码:
const int maxn = 3000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int n, m;
char s[maxn];
bitset<805> a[11];
bitset<805> b, pre;
int dp[maxn];
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
n = readint();
m = readint();
scanf("%s", s + 1);
repd(i, 1, m)
{
int num = readint();
while (num--)
{
int x = readint();
a[x][i] = 1;
}
}
pre[0] = 1;
repd(i, 1, n)
{
b = a[s[i] - '0'];
b &= pre << 1;
if (b[m] == 1)
{
dp[i] = dp[i - m] + 1;
} else
{
dp[i] = dp[i - 1];
}
pre = b;
pre[0]=1;
}
if (dp[n] == 0)
{
printf("Failed to win the prize\n");
} else
{
printf("%d\n", dp[n] );
}
return 0;
} F-Animal Protection
思路：
是单调栈的经典题目，也是一个原题的更改版本，详见：
https://www.cnblogs.com/qieqiemin/p/13164440.html
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 1
bool mpa[3005][3005];
ll height[3005];
ll STK[3005], ANS[3005], head;
char s[1005][1005];
const ll mod = 1000000007;
int main()
{
int n, m;
n = readint();
m = readint();
repd(i, 1, n) {
scanf("%s", s[i] + 1);
}
repd(i, 1, n)
{
repd(j, 1, m)
{
if (s[i][j] == 'X')
{
mpa[i][j] = 0;
} else
{
mpa[i][j] = 1;
}
}
}
long long ans = 0;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if ( !mpa[i][j] )
height[j] = i;
while ( head and height[ STK[head] ] < height[j] )
{
head --;
}
STK[ ++ head ] = j;
ANS[ head ] = ANS[ head - 1 ] + (i - height[STK[head]] ) * ( STK[head] - STK[head - 1] );
ans += ANS[ head ];
ans %= mod;
}
head = 0;
}
cout << ans;
return 0;
} G-XOR
思路：
对于这个数列一定可以找到这个数列的最大值在二进制表示法中最高位之后的所有0位置都为1的数字
答案即为，即最大值
在二进制表示法中最高位以及最高位之后的所有位都为1。
代码：
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
ll n;
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
n = readll();
if (n == 1)
{
printf("%lld\n", 0ll );
return 0;
}
ll x = 0ll;
while (n > 0)
{
x++;
n /= 2;
}
chu(x);
printf("%lld\n", (1ll << (x )) - 1 );
return 0;
} H-Maze
思路：
对于整个迷宫看成图，每个字符作为节点，字符能相互走到的关系作为无向边，该题目则为问每一个节点所属的图中节点个数，直接用并查集将存在边的节点合并为同一个集合，同时维护一下集合的节点个数即可。
代码:
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int far[maxn];
int dsu_sz[maxn];
void dsu_init(int n)
{
repd(i, 0, n)
{
far[i] = i;
dsu_sz[i] = 1;
}
}
int findpar(int x)
{
if (x == far[x])
{
return x;
} else
{
return far[x] = findpar(far[x]);
}
}
void mg(int x, int y)
{
x = findpar(x);
y = findpar(y);
if (x == y)
return;
if (dsu_sz[x] > dsu_sz[y])
{
dsu_sz[x] += dsu_sz[y];
far[y] = x;
} else
{
dsu_sz[y] += dsu_sz[x];
far[x] = y;
}
}
int n, m;
int q;
char s[3004][3004];
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
n = readint();
m = readint();
q = readint();
repd(i, 1, n)
{
scanf("%s", s[i] + 1);
}
dsu_init(n * m);
repd(i, 1, n)
{
repd(j, 1, m)
{
if (i + 1 <= n && s[i][j] != s[i + 1][j])
{
mg(m * (i - 1) + j, m * (i) + j);
}
if (j + 1 <= m && s[i][j] != s[i][j + 1])
{
mg(m * (i - 1) + j, m * (i - 1) + j + 1);
}
}
}
int x, y;
while (q--)
{
x = readint();
y = readint();
printf("%d\n", dsu_sz[findpar(m * (x - 1) + y)] );
}
return 0;
} I-Prime
思路：
线性筛一下质数，然后求个前缀和即可。
代码：
const int N = 10000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int no[N];
int tot;
int sshu[N];
int sum[N];
void prepare()
{
for (int i = 2; i < N; i++)
{
if (!no[i])
sshu[++tot] = i;
for (int j = 1; j <= tot && sshu[j]*i < N; j++)
{
no[sshu[j]*i] = 1;
if (i % sshu[j] == 0)
{
no[sshu[j]*i] = 1;
break;
}
}
}
for (int i = 2; i < N; i++)
{
sum[i] += sum[i - 1];
if (!no[i])
{
sum[i]++;
}
}
}
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
prepare();
int t;
t = readint();
while (t--)
{
int l = readint();
int r = readint();
printf("%d\n", sum[r] - sum[l - 1] );
}
return 0;
}
J-Compare
思路：
用字符串表示数字，比较大小时，先比较长度，长度如果相等再比较字典序即可。
代码：
#define DEBUG_Switch 0
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
string a, b;
cin >> a >> b;
if (sz(a) > sz(b))
{
cout << ">" << endl;
} else if (sz(a) < sz(b))
{
cout << "<" << endl;
} else
{
if (a == b)
{
cout << "=" << endl;
} else if (a > b)
{
cout << ">" << endl;
} else
{
cout << "<" << endl;
}
}
return 0;
} K-Walk
思路：
从走到
一共有
步，有
步向右走，所以答案为
预处理一下阶乘和逆元即可快速求解。
代码:
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
const ll mod = 1e9 + 7;
ll fac[maxn], inv[maxn];
void pre()
{
fac[0] = 1;
for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod;
inv[maxn - 1] = powmod(fac[maxn - 1], mod - 2, mod);
for (int i = maxn - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(int a, int b)
{
if (b > a || b < 0) return 0;
return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
pre();
int t;
t = readint();
while (t--)
{
int n = readint();
int m = readint();
printf("%lld\n", C(n + m - 2, n - 1) );
}
return 0;
}
L-Defeat the monster
思路：
排序后二分一下，然后维护答案即可。
代码：
int n;
ll a[maxn];
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
n = readint();
repd(i, 1, n)
{
a[i] = readll();
}
sort(a + 1, a + 1 + n);
int ans = 0;
repd(i, 1, n)
{
int pos = upper_bound(a + i, a + 1 + n, a[i] + 5) - a;
ans = max(ans, pos - i);
}
printf("%d\n", ans);
return 0;
} 
京公网安备 11010502036488号