2020-BNUZ-IT節程式設計競賽-題解
A.營救小玉和老爹
B.靜靜想題目
C.年輕人,要來一把昆特牌嗎?
D.我勸,這支蠟燭,耗子尾汁!
E.棋魂
F.英雄聯盟排隊機制
G.arc看演唱會
H.加油,打工人!
I.迪迦的隕石雨
J.新生賽的場外求助
K.測驗接待員
A.營救小玉和老爹
題解
由式子min(ceil((1+T/100)ti), 100100ti),我們可以知道如果在第i條道路清除結束后就通過,那么在該道路耗時就是ti,由此我們對清理計劃進行預處理一下
首先我們對每條路清理計劃按照開始時間進行排序,因為如果不能在下次清除到來前通過該道路,那么就不會走,所以如果兩個相鄰的計劃的間隔時間沒有ti,那么就將他們合并成更大的一個計劃
預處理完,我們就直接跑dij,這里主要在于通過第i條路到達下個點的時間的計算:
我們先二分清理計劃,找到第一個開始時間大于等于當前點的時間計劃a,以及a的前一個計劃b
我們設開始時間為s, 結束時間為f, ti為該道路的無陷阱情況下的通過時間
當前點為cur, 下個點為next
當前點的到達時間為curt, 下個點的抵達時間為nextt
這里有兩種情況:
1. 如果b.f >= curt, 那么nextt = b.f + ti
2. 如果b.f < curt, 那么nextt = min(ceil((1+(curt - b.f)/100)ti), 100100ti)
對于第一種情況,由于我們已經將清理計劃整合合并了,所以如果在b.f通過該道路,可以在a.s前到達next, 這是沒問題的
但是第二種情況,我們其實是需要注意,因為如果 nextt是大于b.f + ti, 那么就不能保證可以在a.s前到達next, 所以我們需要判斷一下是否可以在a.s前到達,不能的話就nextt=a.f+ti
標程
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 100100;
vector<pii> g[N];
ll t[N], dis[N];
vector<pair<ll, ll> > blocks[N];
bool vis[N];
typedef struct node{
ll time;
int point;
bool operator<(const node&a) const{
if(a.time == time){
return a.point < point;
}
return a.time < time;
}
}node;
ll calTime(ll tnow, ll prev, ll ti) {
if(tnow + 100 - prev > 100100 * 100) return ti * 100100;
else if(((tnow-prev)*ti) % 100 == 0) return ti + ((tnow - prev) * ti) / 100;
else return ti + ((tnow - prev) * ti) / 100 + 1;
}
ll getNextTime(vector<pair<ll, ll> > &b, ll cur, ll ti) {
if(b.empty()) {
return cur + calTime(cur, 0, ti);
} else if(cur <= b[0].first) {
ll tmp = cur + calTime(cur, 0, ti);
if(tmp <= b[0].first) return tmp;
else return b[0].second + ti;
}
auto it = lower_bound(b.begin(), b.end(), make_pair(cur,0ll));
it--;
if(it->second >= cur) {
cur = it->second;
}
ll tmp = calTime(cur, it->second, ti);
it++;
return (it == b.end() || (cur + tmp <= it->first)) ? (cur + tmp) : (it->second + ti);
}
ll dijkstra(int n){
for(int i = 1; i <= n; i++){
dis[i] = (1LL << 60);
}
dis[1] = 0;
priority_queue<node >pq;
node tt;
tt.point = 1;
tt.time = 0;
pq.push(tt);
while(!pq.empty()){
node Now = pq.top();
pq.pop();
int x = Now.point;
ll ctime = Now.time;
if(vis[x]) continue;
vis[x] = 1;
for(pii e : g[x]){
int eid = e.first, nxt = e.second;
if(vis[nxt]) continue;
ll ntime = getNextTime(blocks[eid], ctime, t[eid]);
if(dis[nxt] > ntime){
dis[nxt] = ntime;
node temp;
temp.point = nxt;
temp.time = ntime;
pq.push(temp);
}
}
}
return dis[n];
}
void clean(vector<pair<ll, ll> > &v, ll ti) {
if(v.empty()) return;
pair<ll, ll> p = v[0];
vector<pair<ll, ll> > newv;
int len = v.size();
for(int i = 1; i < len; i++) {
if(p.second + ti < v[i].first) {
newv.push_back(p);
p = v[i];
} else {
p.second = v[i].second;
}
}
newv.push_back(p);
v = newv;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d%lld", &a, &b, &t[i]);
g[a].push_back(make_pair(i,b));
g[b].push_back(make_pair(i,a));
}
int k;
scanf("%d", &k);
for(int i = 0; i < k; i++) {
int id, s, f;
scanf("%d%d%d", &id, &s, &f);
blocks[id].push_back(make_pair(s,f));
}
for(int i = 1; i <= m; i++) {
sort(blocks[i].begin(), blocks[i].end());
clean(blocks[i], t[i]);
}
ll ans = dijkstra(n);
printf("%lld", ans);
return 0;
}
B.靜靜想題目
題解
后綴自動機+線段樹合并
標程
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#define pr pair<int,int>
#define mp make_pair
#define ll long long
#define IT vector< pr > :: iterator
#define N 500005
#define qN 100005
using namespace std;
int l, r;
int lth[qN], g[N];
ll ans[qN];
char s[N];
string T[qN];
vector< pr >e[N];
int n, q;
struct SAM {
int lst = 1, cnt = 1, tr[N << 1][26], pre[N << 1], len[N << 1], lc[N << 1];
void ins(int c) {
int p = lst, q, np;
lst = np = ++cnt;
len[np] = len[p] + 1, lc[np] = len[p];
for (; p && !tr[p][c]; p = pre[p])
tr[p][c] = np;
if (!p)
pre[np] = 1;
else {
q = tr[p][c];
if (len[p] + 1 == len[q])
pre[np] = q;
else {
int g = ++cnt;
memcpy(tr[g], tr[q], sizeof(tr[q]));
len[g] = len[p] + 1, pre[g] = pre[q], lc[g] = lc[q];
for (; p && tr[p][c] == q; p = pre[p])
tr[p][c] = g;
pre[np] = pre[q] = g;
}
}
}
void Clear() {
memset(tr, 0, 26 * (cnt + 1)*sizeof(int));
cnt = lst = 1;
}
} S1, S2;
#define ls(x) a[x].ch[0]
#define rs(x) a[x].ch[1]
#define fa(x) a[x].f
#define tag(x) a[x].cltg
#define col(x) a[x].cl
struct LCT {
int ch[2], f, cltg, cl;
} a[N << 1];
int Q[N << 1];
int id(int x) {
return ls(fa(x)) == x ? 0 : 1;
}
bool isrt(int x) {
return ls(fa(x)) != x && rs(fa(x)) != x;
}
void connect(int x, int F, int son) {
fa(x) = F;
a[F].ch[son] = x;
}
void rot(int x) {
int y = fa(x), r = fa(y);
int yson = id(x), rson = id(y);
if (isrt(y))
fa(x) = r;
else
connect(x, r, rson);
connect(a[x].ch[yson ^ 1], y, yson);
connect(y, x, yson ^ 1);
}
void push_tag(int x, int z) {
if (!x)
return;
tag(x) = col(x) = z;
}
void push_down(int x) {
if (tag(x)) {
push_tag(ls(x), tag(x));
push_tag(rs(x), tag(x));
tag(x) = 0;
}
}
void splay(int x) {
int g = x, k = 0;
Q[++k] = x;
while (!isrt(g))
g = fa(g), Q[++k] = g;
while (k)
push_down(Q[k--]);
while (!isrt(x)) {
int y = fa(x);
if (isrt(y))
rot(x);
else if (id(x) == id(y))
rot(y), rot(x);
else
rot(x), rot(x);
}
}
void access(int x, int r) {
int y;
for (y = 0; x; y = x, x = fa(x)) {
splay(x);
rs(x) = y;
}
push_tag(y, r);
}
int Col(int x) {
splay(x);
return col(x);
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i)
S1.ins(s[i] - 'a');
for (int i = 2; i <= S1.cnt; ++i)
fa(i) = S1.pre[i];
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
cin >> T[i];
lth[i] = T[i].length();
scanf("%d%d", &l, &r);
e[r].push_back(mp(l, i));
}
int st = 1;
for (int i = 1; i <= n; ++i) {
st = S1.tr[st][s[i] - 'a'];
access(st, i);
for (IT it = e[i].begin(); it != e[i].end(); ++it) {
S2.Clear();
int l = it->first, w = it->second, s0 = 1, st0 = 1, nlen = 0;
for (int j = 0; j < lth[w]; ++j)
S2.ins(T[w][j] - 'a');
for (int j = 0; j < lth[w]; ++j) {
int c = T[w][j] - 'a';
st0 = S2.tr[st0][c];
if (!S1.tr[1][c] || Col(S1.tr[1][c]) < l)
s0 = 1, nlen = 0;
else {
while (!S1.tr[s0][c])
s0 = S1.pre[s0], nlen = S1.len[s0];
s0 = S1.tr[s0][c];
++nlen;
if (Col(s0) - nlen + 1 < l) {
while (Col(s0) - S1.len[S1.pre[s0]] < l)
s0 = S1.pre[s0];
nlen = min(S1.len[s0], Col(s0) - l + 1);
}
}
g[j] = nlen;
}
for (int j = 2; j <= S2.cnt; ++j)
ans[w] += max(S2.len[j] - max(g[S2.lc[j]], S2.len[S2.pre[j]]), 0);
}
}
for (int i = 1; i <= q; ++i)
printf("%lld\n", ans[i]);
return 0;
}
C.年輕人,要來一把昆特牌嗎?
題解
有n張牌,兩個人輪流取牌,每次可以選擇取1、2、k張牌,取走最后一張牌的人輸掉比賽,兩個人都表現最佳的情況下,誰能贏,
狀態轉移
標程
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
int arr[10],dp[maxn];
int main() {
int t;
cin >> t;
while(t--) {
int n,k;
cin >> n >> k;
arr[0] = 1;
arr[1] = 2;
arr[2] = k;
dp[1] = 0;
for (int i=2; i<=n; i++) {
dp[i] = 0;
for (int j=0; j<3; j++) {
if((i - arr[j] > 0) && (dp[i-arr[j]] == 0)) {
dp[i]=1;
break;
}
}
}
if(dp[n] == 1) {
puts("df");
}
else {
puts("yst");
}
}
}
D.我勸,這支蠟燭,耗子尾汁!
題解
有一圈蠟燭,首尾相接,蠟燭有點燃和熄滅兩種狀態,其中一個蠟燭的狀態取反,隔壁兩個也會取反,求最少需要多少次能把所有蠟燭改變成同一個狀態,
搜索,深度優先搜索也能過,
列舉每一個蠟燭的狀態,
標程
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int n,ans,arr[maxn];
void change(int idx) {
arr[idx] = !arr[idx];
if(idx - 1 >= 1) {
arr[idx-1] = !arr[idx-1];
}
else {
arr[n] = !arr[n];
}
if(idx + 1 <= n) {
arr[idx+1] = ! arr[idx+1];
}
else {
arr[1] = !arr[1];
}
}
bool check() {
for(int i=1;i<=n;i++) {
if(arr[i] != arr[1]) {
return false;
}
}
return true;
}
void dfs(int idx, int res) {
if(idx == n+1) {
if(check()) {
if(res < ans) {
ans = res;
}
}
}
else {
dfs(idx+1,res);
change(idx);
dfs(idx+1,res+1);
change(idx);
}
}
int main() {
int t;
cin >> t;
while(t--) {
cin >> n;
for(int i=1;i<=n;i++) {
cin >> arr[i];
}
ans = inf;
dfs(1,0);
if(ans == inf) {
puts("-1");
}
else {
cout << ans << endl;
}
}
}
E.棋魂
題解
簡單模擬判斷,使用一個二維陣列存取當前棋盤的狀態,每次添加一顆新的棋子判斷,判斷當前四個方向的棋子有連續的棋子數量是否超過五即可,
標程
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
const int p[4][2] = {{1, 0}, {0, 1}, {1, 1}, {-1, 1}};
int n, m;
char now[maxn][maxn];
bool check(int x, int y){
for (int i = 0; i < 4; i++){
int cnt = -1;
for (int r = x, c = y; r && c && r <= n && c <= n; r -= p[i][0], c -= p[i][1]){
if(now[r][c] == now[x][y]){
cnt++;
} else {
break;
}
}
for (int r = x, c = y; r && c && r <= n && c <= n; r += p[i][0], c += p[i][1]){
if(now[r][c] == now[x][y]){
cnt++;
} else {
break;
}
}
if(cnt >= 5){
return 1;
}
}
return 0;
}
int main(){
cin >> n >> m;
for (int i = 1;i <= m; i++){
int x, y;
cin >> x >> y;
now[x][y] = i & 1 ? 'B' : 'W';
if(check(x, y)){
printf("%s %d\n", i & 1 ? "小胖" : "121", i);
return 0;
}
}
printf("UNK %d\n", m);
return 0;
}
F.英雄聯盟排隊機制
題解
首先考慮如果前后兩個人等待時間相差超過m,那一定不必等,時間要進行一定的排序使用dp,用f[i][j]表示前i個人全送進服務器,且最后一個時間點讓第i個人等了j分鐘,前i個人總共等了多久,那么f[i][j]可以轉移到f[k][下一個時間-tk],表示下一個時間點把k之前包括k的人送了,這里下一個時間點的時間就是f[i][j]表示的最佳時間點(a[i]+j)+m和tk取最大值,多花的時間用前綴和維護一下就行了,
標程
#include<bits/stdc++.h>
using namespace std;
const int maxN = 505, maxM = 205;
int n, m, mm, ans = 1e9, t[maxN], g[maxN][maxM];
int main() {
scanf("%d%d", &n, &m);
mm = m + m;
int max_int = 1e9;
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
}
sort(t + 1, t + n + 1);
for (int i = 1; i <= n; i++) {
g[i][0] = max_int;
for (int j = 0; j <= min(t[i] - t[i - 1] - m, m - 1); j++) {
g[i][0] = min(g[i][0], g[i - 1][j]);
}
for (int j = 1; j < mm; j++) {
g[i][j] = min(g[i][j - 1], t[i] + j - t[i - 1] - m >= 0 &&
t[i] + j - t[i - 1] - m < mm ? g[i - 1][t[i] + j - t[i - 1] - m] : max_int);
}
for (int j = 0; j < mm; j++) {
g[i][j] = min(g[i][j], t[i] + j - t[i - 1] < mm ? g[i - 1][t[i] + j - t[i - 1]] : max_int) + j;
}
}
for (int i = 0; i < m; i++) {
ans = min(ans, g[n][i]);
}
printf("%d", ans);
return 0;
}
G.arc看演唱會
題解
簽到題
標程
#include <bits/stdc++.h>
using namespace std;
int a[111], b[111];
int main(){
long long n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
long long sum = 0;
for(int i = 1; i <= n; i++){
cin >> b[i];
sum += (a[i] - b[i]);
}
cout << (sum >= m * 2LL ? "大耳朵王王" : "alex生日快樂");
}
H.加油,打工人!
題解
有一個長度為n的字串,有最多m次交換相鄰兩個字符機會,也可以不交換,最后給出一個字典序最小的字串,
貪心思想,
為了達到字典序最小,必須盡可能讓前面的字符變小,從前往后找每個位置,找到符合<m的前提下最小的字母,花費m次交換機會到前面一定是最賺的,
標程
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int main() {
int t;
cin >> t;
while(t--) {
int n,m;
cin >> n >> m;
string str;
cin >> str;
for(int i=0;i<n;i++) {
int tmp = i;
int cnt = 0;
for(int j=i+1;j<n && m >= j-i;j++) {
if(str[j] < str[tmp]) {
tmp = j;
cnt = j-i;
}
}
if(str[tmp] == str[i]) continue;
for(int k=tmp;k>i;k--) {
swap(str[k],str[k-1]);
}
m -= cnt;
}
cout << str << endl;
}
}
I.迪迦的隕石雨
題解
整體二分,樹狀陣列實作區間修改單點查詢,然后注意修改是在環上的,
標程
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
LL c[300005];
vector<int> G[300005];
int L[300005], R[300005], val[300005];
int P[300005], ans[300005];
int q[300005], q1[300005], q2[300005];
int n, m, k, now = 0;
inline int read() {
int sum = 0;
char ch = 0;
while (ch > '9' || ch < '0')
ch = getchar();
while (ch >= '0' && ch <= '9')
sum = sum * 10 + ch - '0', ch = getchar();
return sum;
}
inline int lowbit(int x) {
return x & -x;
}
inline void add(int x, int v) {
for (; x <= m; x += lowbit(x))
c[x] += v;
}
inline LL query(int x) {
LL tmp = 0;
for (; x > 0; x -= lowbit(x))
tmp += c[x];
return tmp;
}
inline void update(int l, int r, int v) {
if (l <= r)
add(l, v), add(r + 1, -v);
else
add(1, v), add(r + 1, -v), add(l, v), add(m + 1, -v);
}
void solve(int l, int r, int s, int t) { /// lr流星雨區間 mid答案 st未解決的國家區間
if (l > r || s > t)
return;
if (l == r) {
for (int i = s; i <= t; ++ i)
ans[q[i]] = l;
return;
}
int mid = (l + r) >> 1;
///now是當前次數,mid是列舉次數
while (now < mid)
now++, update(L[now], R[now], val[now]);
while (now > mid)
update(L[now], R[now], -val[now]), now--;
int s1 = 0, s2 = 0;
///劃分籃子
for (int i = s; i <= t; ++ i) {
LL tmp = 0;
int x = q[i];
for (int j = 0; j < G[x].size(); j++) {
tmp += query(G[x][j]);
if (tmp >= P[x])
break;
}
if (tmp >= P[x])
q1[++s1] = x; ///這個國家已經滿足需求,放入左籃子
else
q2[++s2] = x;///沒滿足就放入右邊的籃子
}
///放入籃子
for (int i = 1; i <= s1; i++)
q[s + i - 1] = q1[i];
for (int i = 1; i <= s2; i++)
q[s + s1 + i - 1] = q2[i];
solve(l, mid, s, s + s1 - 1);
solve(mid + 1, r, s + s1, t);
}
int main() {
n = read(), m = read();
for (int i = 1; i <= m; i++)
G[read()].push_back(i);
for (int i = 1; i <= n; i++)
P[i] = read(), q[i] = i;
k = read();
for (int i = 1; i <= k; i++)
L[i] = read(), R[i] = read(), val[i] = read();
solve(1, k + 1, 1, n);
for (int i = 1; i <= n; i++) {
if (ans[i] == k + 1)
printf("NO\n");
else
printf("%d\n", ans[i]);
}
return 0;
}
J.新生賽的場外求助
題解
設負數數量為cnt
- n%2 == 1
1.1. cnt <= n/2,先將(全部負數)與正數取反,得到 cnt>=n/2;
1.2. cnt > n/2,每次取(n/2個負數)與正數取反,每次增加1個負數,直到cnt==n;
1.3. cnt > n,先對n個負數取反,得到cnt<n(情況1.1,1.2);
1.4. cnt == n,直接全部負數取反,陣列全為正數;
可見最終陣列將全部都為正數 - n%2 == 0
與第一種情況n%2 == 1類似,不過由于每次取((n/2-1)個負數)與正數取反時增加的負數數量是2個,
所以當cnt%2 == 1,即奇數時,最侄訓留下一個負數,我們就將絕對值最小的給到這個負數
當cnt%2==0,即偶數時,則可以將陣列每個數都該變成正數
標程
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
int a[N];
int main(){
int n;
scanf("%d", &n);
long long sum = 0, cnt = 0;
int minn = 0x3f3f3f3f;
for(int i = 0; i < 2*n-1; i++) {
scanf("%d", &a[i]);
sum += abs(a[i]);
minn = min(minn, abs(a[i]));
if(a[i] < 0){
cnt++;
}
}
sort(a, a + 2*n-1);
if(n % 2){
printf("%lld", sum);
} else {
printf("%lld", cnt % 2 ? sum - minn - minn : sum);
}
}
K.測驗接待員
題解
拉格朗日四平方和定理:每個正整數均可表示為4個整數的平方和,如果不能表示成更少的數的平方之和,必定滿足(4^a)*(8m+7)
該定理就是說:一個正整數最少只能被表示為4個整數的平方和的充要條件是該數滿足(4^a) *(8m+7)
若一個數最少由1個數的平方組成,我們直接sqrt就可以得到
若最少由2個陣列成,因為數的范圍1e15,我們可以sqrt后列舉得到
而若最少只能由4個數,那么他肯定是滿足(4^a) *(8m+7)的數,
那么剩下的就是最少由3個數的平方和組成的了
標程
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n;
scanf("%lld",&n);
ll k1 = sqrt(n);
if(k1 * k1 == n) {
printf("1");
return 0;
}
ll m;
for(ll x = k1; x >= 1; x--) {
m = n - x * x;
ll k2 = sqrt(m);
if(x * x + k2 * k2 == n) {
printf("2");
return 0;
}
}
m = n;
while(m % 4 == 0) m /= 4;
if(m % 8 == 7) {
printf("4");
return 0;
}
printf("3");
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/231505.html
標籤:其他
下一篇:JAVA作業——紅包分發
