這篇題解是賽前寫的（最后一題是后來加的不算… …），預測rk1AK，四題五人以內，半數以上人員一
兩題及以下… …
每個人都應該具有的水準為四題，第五題素數篩只提到過，還沒講過，但不是很難，希望大家能夠賽后自學，第六題初次寫的話思維和代碼能力要求較大，
A.CodeForces - 1A
一個長為n，寬為m的廣場，至少用多少塊邊長為a的長方形瓷磚能將廣場完全覆寫，
5*5的廣場用邊長為2的瓷磚覆寫需要9塊，
AC代碼：
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n, m, a;
scanf("%lld%lld%lld", &n, &m, &a);
printf("%lld\n", (n / a + (n % a ? 1 : 0)) * (m / a + (m % a ? 1 : 0)));//三目寫法更簡潔
// long long A, B;
// A = n / a;
// if (n % a > 0)
// A++;
// B = m / a;
// if (m % a > 0)
// B++;
// printf("%lld\n", A * B);
return 0;
}
B.CodeForces - 1036D
給定兩個陣列， 每次可以將連續的一段合并起來變成這一段的和，問最終最多可以分成多少段，使得得到的兩個陣列一樣，無法滿足情況輸出-1，
例如樣例一：
原陣列：
11 2 3 5 7
11 7 3 7
將陣列1的2 3 5合并成10
將陣列2的7 3合并成10
11 10 7
11 10 7
最大長度是3
顯然，如果兩個陣列和都相同，那么全部合并就滿足情況，因此只有兩個陣列和不同時才輸出-1，
滿足情況時，又要使長度最大，只需要貪心的從前往后合并，不斷執行以下操作：
1.兩陣列前綴和相同時分成一段，
2.不相同時，前綴和小的往后繼續合并，
AC代碼：
#include <bits/stdc++.h>
using namespace std;
int a[300010];
int b[300010];
int main()
{
int n, m;
long long s1 = 0, s2 = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
s1 += a[i];
}
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
scanf("%d", &b[i]);
s2 += b[i];
}
if (s1 != s2)
return printf("-1\n"), 0;
s1 = s2 = 0; //a陣列和s1，b陣列和s2
int pos1 = 0, pos2 = 0, ans = 0;
while (pos1 <= n || pos2 <= m)
{
if (s1 == s2 && s1) //前綴和相同，分成一段
{
++ans, ++pos1, ++pos2;
s1 = a[pos1];
s2 = b[pos2];
}
else if (s1 == s2 && !s1)
{
s1 += a[++pos1];
s2 += b[++pos2];
}
else if (s1 < s2) //s1小，往后合并一個a元素
s1 += a[++pos1];
else if (s1 > s2) //s2小，往后合并一個a元素
s2 += b[++pos2];
}
printf("%d\n", ans);
return 0;
}
C.CodeForces - 669C
題面勸退系列
其實題目很簡單，剛開始有一個矩陣，有三種操作：
- 第一種是把行往右移動一個位置，最后一個補到第一個位置，
- 第二種是把列往下移動一個位置，最后一個補到第一個位置，
- 第三種是第 i i i行第 j j j列元素是 x x x，
讓你給出一種滿足題目的原矩陣，
先簡化一下問題，如果是一維的陣列，比如原序列是：
a b c d e
現在將序列向右移動一次
e a b c d
然后告訴你第三個數是x，
再將序列向右移動一次
e a b c d
然后告訴你第一個數是y，
讓你找到x、y在最開始的序列中的位置，
顯然倒著來模擬一遍就行：
告訴你第一個數是y： y # # # #
將序列向左移動一次：# # # # y
告訴你第三個數是x： # # x # y
將序列向左移動一次：# x # y #
序列#x#y#就滿足題意，其中#填任何數字都可以，
只需拓展到二維進行模擬，就是正解，
AC代碼：
#include <bits/stdc++.h>
using namespace std;
int mp[105][105];
int ctr[10005][10];
int main()
{
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= q; i++)
{
scanf("%d", &ctr[i][1]);
if (ctr[i][1] != 3)
scanf("%d", &ctr[i][2]);
else
scanf("%d %d %d", &ctr[i][2], &ctr[i][3], &ctr[i][4]);
}
for (int i = q; i >= 1; i--)
{
if (ctr[i][1] == 1)
{
int temp = mp[ctr[i][2]][m];
for (int j = m; j >= 2; j--)
mp[ctr[i][2]][j] = mp[ctr[i][2]][j - 1];
mp[ctr[i][2]][1] = temp;
}
else if (ctr[i][1] == 2)
{
int temp = mp[n][ctr[i][2]];
for (int j = n; j >= 2; j--)
mp[j][ctr[i][2]] = mp[j - 1][ctr[i][2]];
mp[1][ctr[i][2]] = temp;
}
else
mp[ctr[i][2]][ctr[i][3]] = ctr[i][4];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
printf("%d ", mp[i][j]);
printf("\n");
}
return 0;
}
D.CodeForces - 760B
題意不說了，考察的演算法題目給了，二分答案，難點在于check的寫法，
貪心的考慮，最節省枕頭的方案就是第k個人拿了x個枕頭，兩邊的人不斷遞減1但不小于1，
下面的幾種情況都是滿足條件的分配：
情況1：2 3 4 3 2
情況2：1 1 1 1 2 3 4 3 2 1
情況3：5 4 3 2 1 1 1
因此，我們二分出第k個人拿了mid個枕頭，這時需要計算滿足分配的最小枕頭數量sum，并通過這個sum調整上下界，計算這個sum就是這題的關鍵，顯然可以分成左右兩邊計算，兩邊都是一個公比為1的等引數列，不過要考慮最后有沒有遞減成1，比如上面的情況1和1情況2，
AC代碼：
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n, m, k, ans = 0;
scanf("%lld %lld %lld", &n, &m, &k);
m -= n; //預處理 每個人都先拿到一個枕頭
long long left = k; //這個人以及他左邊總共有多少人
long long right = n - k + 1; //這個人以及他右邊總共有多少人
long long l = 1, r = m;
while (l <= r)
{
long long mid = l + r >> 1;
//check
long long ned = 0;
if (left <= mid)
{
long long temp = mid - left;
ned += (mid * (mid + 1)) / 2 - (temp * (temp + 1)) / 2;
}
else
{
ned += (mid * (mid + 1)) / 2;
}
if (right <= mid)
{
long long temp = mid - right;
ned += (mid * (mid + 1)) / 2 - (temp * (temp + 1)) / 2;
}
else
{
ned += (mid * (mid + 1)) / 2;
}
ned -= mid;
//改變左右界
if (ned <= m)
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
printf("%d\n", ans + 1);
return 0;
}
E.LightOJ - 1259
判斷一個數n能被多少對素數相加得到，例如4=2+2，答案就是1，10=3+7=5+5，答案就是2，
先去學歐拉篩，學會了就看代碼吧，
#include <bits/stdc++.h>
using namespace std;
bool getp[10000010]; //getp[x]==0表示x是質數
int preme[1000010], ct;
void pre()
{
getp[0] = getp[1] = 1;
for (int i = 2; i <= 10000000; i++) //歐拉篩篩質數
if (!getp[i])
{
preme[++ct] = i;
for (int j = 2; j * i <= 10000000; j++)
getp[i * j] = 1;
}
}
int main()
{
pre(); //預處理質數
int t, CA = 0;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
int ans = 0;
for (int i = 1; i <= ct && preme[i] <= n / 2; i++)
if (!getp[n - preme[i]])
ans++;
printf("Case %d: %d\n", ++CA, ans);
}
return 0;
}
F.計蒜客 - A1139
并查集、DFS都可以寫，初次寫這題的話，思維和代碼能力要求較高 ，比賽時不會寫正常， 可以參考網上的各種博客，
AC代碼：
/*
* @Author: hesorchen
* @Date: 2020-12-30 16:53:18
* @LastEditTime: 2021-01-13 22:49:07
* @Description: 栽種絕處的花
*/
#include <bits/stdc++.h>
using namespace std;
char mp[1010][1010];
bool c[1010], r[1010];
int n, m, ans;
void dfs(int x, int y, int is)
{
for (int i = 1; i <= n; i++)
{
if ((is || (!c[i] || !r[y])) && mp[i][y] == '1')
{
c[i] = r[y] = 1;
dfs(i, y, 0);
}
}
for (int j = 1; j <= m; j++)
{
if ((is || (!c[x] || !r[j])) && mp[x][j] == '1')
{
c[x] = r[j] = 1;
dfs(x, j, 0);
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", mp[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (!c[i] && !r[j] && mp[i][j] == '1')
{
c[i] = r[j] = 1;
dfs(i, j, 1);
ans++;
}
}
printf("%d\n", ans);
return 0;
}
總結：這次比賽難度不低，尤其是對未加入作業室的同學，沒打好的同學不要氣餒，補題補知識點才是關鍵，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249940.html
標籤：其他
上一篇：python小練習
下一篇：MFC雙人五子棋