比賽鏈接
感謝出題人手下留情，第一次補完所有題，著實開心，
個人感覺這場比賽題目難度大概對應CF的div3吧，
A 切蛋糕
題目：
第一題本來打算開它的，兩分鐘沒啥頭緒，就跳了，賽后看大佬們的代碼，好家伙，我直接好家伙，上來就是暴力，先切2047次，把蛋糕切成2048塊（也就是2的16次方，比題目要求的15次方大就行），然后嘛就按照題目意思去解方程：|x/2048-1/k|<=1/2^10，最后回圈k次，每次將x個蛋糕打包，回圈的時候用到了左移位，不太懂位運算的同學可以參考這篇博客（click here），里面介紹的很全哦~，
Code：
int main() {
int k;
cin >> k;
cout << k + 2047 << endl;
for (int i = 0; i < 11; i++)
for (int j = 1; j <= (1<<i); j++)
cout << 1 << ' ' << i << endl;
int x = (1<<11) / k;
for (int i = 1; i <= k; i++) {
cout << 2 << ' ' << x << ' ';
for (int j = 1; j <= x; j++) cout << "11 ";
cout << endl;
}
return 0;
}
B 小寶的幸運陣列
就是要求能被k整除的最大連續子陣列的長度嘛，資料范圍這么大，暴力必TLE，可以先用sum[]去記錄前i項的和，假設前m項的和取模k得到x, 前n項的和取模k得到的也是 x, 那么m+1-n這個子序列的和肯定是能夠被k整除的，想到這個那么問題就很簡單了，
Code：
ll a[100005], sum[100005];
ll pos[100005];
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
mem(pos, INF);
ll ans = -1;
for (int i = 1; i <= n; i++) {
ll m = sum[i] % k;
if (m == 0) ans = max(ans, 1ll*i);
if (pos[m] != INF) ans = max(ans, i - pos[m]);
pos[m] = min(pos[m], 1ll*i);
}
cout << ans << endl;
}
return 0;
}
C 上進的凡凡
直接記錄每段非降序子陣列長度，然后(1+len)*len/2求出該段對應個數累加即可，
Code：
struct node {
ll len;
}e[100005];
ll sum(ll len) {
return (1+len)*len/2;
}
ll a[100005];
int main() {
int n, id = 1, pos = 1;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
e[i].len = 1;
}
a[n+1] = -INF;
for (int i = 1; i <= n; i++)
if (a[i]<=a[i+1]) {
e[id].len++;
} else id++;
ll ans = 0;
for (int i = 1; i < id; i++)
ans += sum(e[i].len);
cout << ans << endl;
return 0;
}
D Seek the Joker I
巴什博弈，老經典的博弈入門題了，只是把取光者剩改成取最后一個敗，其實原理是一樣的，對于這題來說，n % (k + 1) == 1就是一個必敗點嘛，
Code：
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
if (n == 1) cout << "ma la se mi no.1!" << endl;
else if (n <= k)
cout << "yo xi no forever!" << endl;
else {
int tmp = n % (k + 1);
if( tmp == 1 )
cout << "ma la se mi no.1!" << endl;
else
cout << "yo xi no forever!" << endl;
}
}
return 0;
}
E Seek the Joker II
兩堆石子，一堆k-1，另一堆n-k，先取到任意一堆的最后一個輸，emm，這不是威佐夫博弈嘛，啪的一下就AC了，很快啊~
Code：
const double GSR=(1+sqrt(5.0))/2;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int a = k-1, b = n-k;
if(a > b) swap(a, b);
if(a == (int)(GSR*(b-a)))
cout << "ma la se mi no.1!" << endl;
else
cout << "yo xi no forever!" << endl;
}
return 0;
}
F 成績查詢ing
交了一發暴力，先TLE為敬，然后就掏出了C with STL的傳統藝能map+set，想著應該能過，結果還是TLE了，補題的時候才發現，，，把endl改成"\n"直接就能過，emm，這又是什么玄學，然后聽說endl要比"\n"慢一些，然后嘛，，，反手就加了一句
#define endl “\n”
（畢竟瘋起來連int都define成longlong手動狗頭）
Code：
struct node {
string name;
int grade, sex, sno;
}s[100005];
int cmp(node a, node b) {
return a.name<b.name;
}
map<string, node> m;
set<string> se[200];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> s[i].name >> s[i].grade >> s[i].sex >> s[i].sno;
sort(s, s+n, cmp);
for (int i = 0; i < n; i++) {
m[s[i].name] = s[i];
se[s[i].grade].insert(s[i].name);
}
int t;
cin >> t;
while (t--) {
int op;
cin >> op;
if (op == 1) {
string str;
cin >> str;
node tmp = m[str];
if (tmp.sno != 0) {
cout << tmp.grade << ' ' << tmp.sno << ' ' << tmp.sex <<endl;
}
} else {
int grade;
cin >> grade;
set<string>::iterator it;
it = se[grade].begin();
for(;it!=se[grade].end();it++)
cout<<*it<<endl;
}
}
return 0;
}
G 貪吃的派蒙
假設派蒙的位置為p，那如果p-1>k（這種情況下回圈不足一個周期），那就意味著還沒輪到他就已經沒了（他前面那個人洗碗），或者（回圈了至少一個周期）左邊人的最大總和要小于k，這種情況下還是輪不到他洗碗，至于其余情況，則他必洗碗，
Code：
ll s[100005];
int main(){
int q;
cin >> q;
while (q--) {
int n, k;
cin >> n >> k;
int m = 0, p;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x > m) {
m = x;
p = i;
}
s[i] = s[i-1] + x;
}
if (p > k+1 || (s[n] >= k && s[p-1] < k)) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}
H 數羊
直接根據題目給出來的公式寫個dfs就行了，
Code：
const ll mod = 998244353;
ll dfs(int n, int m) {
if (n == 1 && m == 0) return 2;
if (n == 0 && m >= 0) return 1;
if (n >= 2 && m == 0) return n+2;
if (m == 1) return (2*n)%mod;
return dfs(dfs(n-1, m), m-1)%mod;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
cout << dfs(n, m) % mod << endl;
}
return 0;
}
I 買花
emm，等比數列前n項和，直接暴力遍歷一遍（總共才15天嘛），
Code：
int qpow(int a, int n) {
int ans = 1, base = a ;
while (n) {
if (n & 1)
ans = (ans * base) ;
base = (base * base);
n >>= 1;
}
return ans;
}
int main() {
int t, n;
cin >> t;
while (t--) {
cin >> n;
int flag = 0;
for (int i = 2; i <= 15; i++) {
int k = pow(2,i)-1;
if (n%k == 0) {
flag = 1;
break;
}
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
J 這是一題簡單的模擬
正如題名所述，”這是一道簡單的模擬“，出題人誠不欺我，照著題目要求碼一遍就好了，如果WA了，就多看幾遍題目，
Code：
int mp[305][305];
int a[2005], v[305];
int main() {
int N, M;
cin >> N >> M;
mem(mp, -1);
for (int i = 0; i < M; i++) {
int u, v, w;
cin >> u >> v >> w;
mp[u][v] = mp[v][u] = w;
}
int k, ans = INF;
cin >> k;
for (int j = 0; j < k; j++) {
mem(v, 0);
mem(a, 0);
int n, bol = 1;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
v[a[i]]++;
if (v[a[i]]>1) bol = 0;
}
for (int i = 1; i <= N; i++) {
if (v[i] != 1) {
bol = 0;
break;
}
}
if (bol == 0) continue;
bol = 1;
int sum = 0;
a[0] = a[n+1] = 0;
for (int i = 1; i <= n+1; i++) {
if (mp[a[i]][a[i-1]] == -1) {
bol = 0;
break;
} else {
sum += mp[a[i-1]][a[i]];
}
}
if (bol) {
ans = min(ans, sum);
}
}
if (ans != INF) cout << ans << endl;
else cout << -1 << endl;
return 0;
}
K 黑洞密碼
感覺這和上一題差不多，就差把 ”這是道模擬題“ 寫在題面上了，對著題目要求直接碼一遍就行了，
Code：
char s1[100],s2[100],s3[100];
int main() {
cin >> s1;
int l = 0, r = 0, len = strlen(s1);
for (int i = 0; i < len; i++)
if (s1[i] >= '0' && s1[i] <= '9') s2[l++] = s1[i];
else s3[r++] = s1[i];
for (int i = 0; i < r; i++) {
if (s3[i] >= 'a' && s3[i] <= 'z') {
s3[i] -= 'a';
s3[i] = s3[i] + s2[i] - '0';
if (s3[i] >= 26) {
s3[i] %= 26;
if (s3[i] == 25) s3[i] = 'b';
else s3[i] += 'B';
} else s3[i] += 'a';
} else {
s3[i] -= 'A';
s3[i] = s3[i] + s2[i] - '0';
if (s3[i] >= 26) {
s3[i] %= 26;
if (s3[i] == 25) s3[i] = 'B';
else s3[i] += 'b';
} else s3[i] += 'A';
}
}
for (int j = 4; j <= 16; j += 4)
for (int i = j-1; i >= j-4; i--)
cout << s3[i];
return 0;
}
L 建立火車站
先用節點存城市與城市之間的距離（sum）、被分成段的長度（val）以及它們之間站臺數+1（len），然后拿優先佇列存節點，按val降序排列，回圈k次每次取val最大的，并彈出節點，len++，更新val（val=sum/len），再把新的節點push進去，最后隊頂的val就是答案（當然啦，如果最后的val是小數，那么結果應該是val的整數部分+1），
Code：
struct node {
friend bool operator< (node a, node b) {
return a.val < b.val;
}
ll len;
long double val, sum;
};
priority_queue<node> q;
ll dt[100005], a[100005];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a+n);
for (int i = 1; i < n; i++)
dt[i] = a[i]-a[i-1];
for (int i = 1; i < n; i++) {
node tmp;
tmp.val = tmp.sum = dt[i];
tmp.len = 1;
q.push(tmp);
}
while (k--) {
node tmp = q.top();
q.pop();
tmp.len++;
tmp.val = tmp.sum/tmp.len;
q.push(tmp);
}
node ans = q.top();
ll key = (ll)ans.val;
if (ans.val == key) cout << key << endl;
else cout << key+1 << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255303.html
標籤：其他
上一篇：簡化版掃雷詳細解