文章目錄

• 比賽鏈接
• • A CodeForces 1481D AB Graph
  • • 題意：
    • 題解：
    • 代碼：
  • B CodeForces 1481E Sorting Books
  • • 題意：
    • 題解：
    • 代碼：
  • C CodeForces 1478D Nezzar and Board
  • • 題意：
    • 題解：
    • 代碼：
  • D CodeForces 1478C Nezzar and Symmetric Array
  • • 題意：
    • 題解：
    • 代碼：
  • E CodeForces 1478E Nezzar and Binary String
  • F CodeForces 1481C Fence Painting
  • • 題意：
    • 題解：
    • 代碼：
  • G CodeForces 1477E Nezzar and Tournaments
  • H CodeForces 1481F AB Tree
  • I CodeForces 1478B Nezzar and Lucky Number
  • • 題意：
    • 題解：
    • 代碼：
  • J CodeForces 1478F Nezzar and Nice Beatmap
  • K CodeForces 1477D Nezzar and Hidden Permutations
  • L CodeForces 1481B New Colony
  • • 題意：
    • 題解：
    • 代碼：

比賽鏈接

CF699 div2（沒有A題），CF698div2（沒有A題），CF698div1

A CodeForces 1481D AB Graph

題意：

一張完全圖的每一條有向邊上寫著a或者b,問能否構造一條邊數為m的不間斷路線使該路線為回文串

題解：

構造題
對于邊數為奇數的回文串，隨便找兩個點都是可以構造出來的（如果兩點間的兩條邊相同，那么肯定是回文串，如果不相同，形如aba也可以構成回文串）
對于邊數為偶數的回文串，如果是偶數，那么中間兩個肯定是相同的，我們只要找到連著相同的兩條邊就可以。而這種情況在三元環之間肯定能形成這種情況（因為一共就兩種邊，所以肯定有相鄰的邊是一樣的），所以當n >= 3時肯定可以構造出來
當n = 2 的情況，m為奇數討論過（肯定行），m為偶數的話，兩點之間的邊必須相同才行（也就是雙向邊必須一樣）

代碼：

#include <bits/stdc++.h> using namespace std; #define fi first #define se second const int N = 1e6 + 10; const int M = 5e5 + 10; const int INF = 0x3f3f3f3f; const double eps = 1e-4; const int MOD = 1e9+7; typedef long long ll; typedef pair<int, int> PII; char mp[1005][1005]; int main() {int T; cin >> T;while (T--) {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) cin >> mp[i] + 1;if (m & 1) {cout << "YES" << endl;for (int i = 1; i <= m+1; i++) cout << i % 2 + 1 << " ";cout << endl;continue;}if (n == 2) {if (mp[1][2] == mp[2][1]) {cout << "YES" << endl;for (int i = 1; i <= m+1; i++) cout << i % 2 + 1 << " ";cout << endl;}else cout << "NO" << endl;} else {cout << "YES" << endl;int flag;if (mp[1][2] == mp[2][3]) flag = 1;else if (mp[3][1] == mp[1][2]) flag = 0;else flag = 2;for (int i = 0; i <= m; i++) cout << (flag + i + m) % 3 + 1 << " ";cout << endl;}} }

B CodeForces 1481E Sorting Books

題意：

一排書架上有 n 本書排成一排，每本書上有一個顏色ai ，你可以每次將一本書移動到書架的最右端，如果書架上的書，顏色相同的書都排到了一塊，我們就認為他是漂亮的，請問將這個書架通過上面的那一種操作排成漂亮的書架，最少需要幾次操作？

題解：

代碼：

C CodeForces 1478D Nezzar and Board

題意：

n個數組x1 ~ xn，每次可以選擇其中兩個數x和y，然后將2x-y的值加入到數組中，x和y依舊保留，問通過這系列操作是否能得到數字k

題解：

我們先講個定理，裴蜀定理：

設a，b是不全為0的整數，則存在整數x，y，使得ax+by = gcd(a,b)

n個整數間的裴蜀定理：

設a1,a2,a3…an為n個整數，d是它們的最大公約數，那么存在整數x1…xn使得x1 * a1+x2 * a2+…xn * an=d

（證明略）
題目給的是2x-y,我們將其拆開x+(x-y),相當于x加上x與y的差值，其實就是本身加上本身與其他數的差值，我們可以處理出所有的差值，但是O(n²)肯定不行（數據范圍是1e5），其實不用求出所有差值，因為我們求出a1和a2的差值，a2和a3的差值，也就相當于求出a3和a1的差值（a3-a2+a2-a1=a3-a1），也就是求出a[i]與a[i+1]的差值（O(n)，共n-1個
然后我們開始思考裴蜀定理，我們現在有n-1個差值（我們設為a1…an-1），gcd是他們的最大公約數，那么存在整數x1,…xn-1，使得x1 * a1+x2 * a2+…xn-1 * an-1=gcd
我們要求的數是k，我們已經有了每個數a[i]，我們需要的是改變值k-a[i]，也就是只要n-1個差值能表示出k-a[i]即可，現在n-1個差值可以表達出gcd，那么k-a[i]只要是gcd的倍數就可以被表示，如果不是則不行

代碼：

#include <bits/stdc++.h> using namespace std; //#define ACM_LOCAL typedef long long ll; typedef pair<int, int> PII; const int N = 2e5 + 10; const int M = 1e6 + 10; const ll INF = 1e18; const double eps = 1e-4; ll d[N];void solve() {int T; cin >> T;while (T--) {ll n, k;cin >> n >> k;for (int i = 1; i <= n; i++) cin >> d[i];ll gcd_ = 0;for (int i = 2; i <= n; i++) gcd_ = __gcd(d[i]-d[i-1], gcd_);int f = 0;for (int i = 1; i <= n; i++) {if ((k - d[i]) % gcd_ == 0) f = 1;}if (f) cout << "YES" << endl;else cout << "NO" << endl;} }int main() {solve();return 0; }

D CodeForces 1478C Nezzar and Symmetric Array

題意：

給定一個長度為2n的序列d,問能否通過上述公式得到a序列，輸出“YES”/“NO”， a序列中必須成對出現相反數，ai = - aj ，而且不能相同

題解：

這個講的很詳細
這個方法也可以
構造題，題目給了d和a的關系，a數組是成對出現的相反數，且均不相同
我們通過a的性質進行反推，推出數組d 應該有哪些性質
（這里直接將結論，具體推導過程在上面的鏈接中有寫）
d數組滿足：
條件一：d是 成對出現
條件二：d都為偶數
條件三：計算過程中的數都是正整數

原始數組a為±2、±7、±9
差值和d為 36 36 46 54 46 54
去重排序除以2（用really數組保存）18 23 27
27/3=9，所以原始數組中最大的數就是9
(23-9)/2=7，所以原始數組中還有一個正數7
(18-9-7)/1=2，所以原始數組中還有一個正數2

所以原始數組為±2、±7、±9，輸出YES

代碼：

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll really[100010]; // Really 記錄真正需要處理的數（表格二左邊的1/2） int main() {int N;cin >> N;while (N--){int n;scanf("%d", &n);bool buxing = 0; //不行的拼音map<ll, int> ma; //用map記錄出現了幾次（條件一）for (int i = 0; i < 2 * n; i++){ll t;scanf("%lld", &t);if (t % 2) //差值和是否為偶數（條件二）buxing = 1;ma[t]++;}int sum = 1;ll realOriSum = 0; // 已經得出的原來的數，上文樣例中便是 9 7 3if (buxing){puts("NO");}else{for (map<ll, int>::iterator it = ma.begin(); it != ma.end(); it++){if (it->second != 2) // 差值和是否都出現了兩處（條件一）buxing = 1;really[sum++] = (it->first) / 2;}if (buxing){puts("NO");}else{for (sum--; sum > 0; sum--){ll all = really[sum] - realOriSum; //減去原來的數if (all % sum) //是否可以整除buxing = 1;ll thisReal = all / sum;//除以當前really數組內數的數量realOriSum += thisReal;//對已求出的數組a求和if (thisReal <= 0)//檢驗計算過程中的數是否都是正整數buxing = 1;}if (buxing){puts("NO");}elseputs("YES");}}}return 0; }

E CodeForces 1478E Nezzar and Binary String

F CodeForces 1481C Fence Painting

題意：

有一個圍欄，每一塊上都有顏色，用A數組來表示，Bob覺得太單調了，他想涂成B數組的顏色。這時候有m個粉刷匠，每個粉刷匠能且只能粉刷一次圍欄，問你通過這m個人的粉刷能否達到Bob的要求。如果可以輸出YES，并把每個粉刷匠粉刷的下標輸出，否則輸出NO。

題解：

因為顏色會覆蓋，所以如果讓后來的工匠染了某塊木板，前面的工匠選擇這塊木板染色便沒有影響，所以我們先把需要進行染色的木板按顏色分類存下來，從后往前掃每位工匠，如果有需要染對應顏色則染，否則選擇之后會有人染的木板，或者選擇相應顏色的不需要染色的木板染上，顏色不會發生變化

代碼：

#include<bits/stdc++.h> #define MAXN 100005 using namespace std; int t,n,m,a[MAXN],b[MAXN],c[MAXN]; queue<int> ve1[MAXN],ve2[MAXN]; int xx,ans[MAXN]; int main() {scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);//a是原本，b是需求，m是改變 for(int i = 1;i <= n;++i){while(!ve1[i].empty())ve1[i].pop();while(!ve2[i].empty())ve2[i].pop();}xx = 0;for(int i = 1;i <= n;++i)scanf("%d",&a[i]);for(int i =1;i <= n;++i){scanf("%d",&b[i]);if(b[i] == a[i])ve1[a[i]].push(i);//已經涂好 elseve2[b[i]].push(i);//需要該顏色 }for(int i = 1;i <= m;++i)scanf("%d",&c[i]);int f = 1;for(int i = m;i >= 1;--i){//xx是可以被涂的地方 if(ve2[c[i]].empty()==0)//即需要該顏色 {int tmp = ve2[c[i]].front();//需要顏色的位置 ans[i] = tmp;xx = tmp;//因為這個地方最后會被改回顏色，所以之前可以涂 ve2[c[i]].pop();}else if(xx)//如果存在可以多涂的地方 {ans[i] = xx;}else if(ve1[c[i]].empty()==0)//涂在該地方沒有影響（相當于在本來是1的地方涂1） {ans[i] = ve1[c[i]].front();xx = ans[i];} else{f = 0;break;}}for(int i = 1;i <= n;++i){if(ve2[i].empty()==0)//如果存在地方改變不了顏色 {f = 0;break;}}if(f){printf("YES\n");for(int i = 1;i <= m;++i)printf("%d ",ans[i]);printf("\n");}elseprintf("NO\n");}return 0; }

G CodeForces 1477E Nezzar and Tournaments

H CodeForces 1481F AB Tree

I CodeForces 1478B Nezzar and Lucky Number

題意：

我們定義一個數字x為最喜歡的數（0<x<9），只要是出現了x的數都是幸運樹，另外如果一個數可以由多個幸運樹相加得到，該數也為幸運數
現給q個數，判斷是否為幸運數

題解：

我的思路是：如果x是最喜歡的數，給數w，先查看w的各位是否有x存在，然后將w減去x，得到z，然后再看z的各位是否存在x，然后再減想，依次循環，直到小于x位置或者確定為幸運數為止
我是這樣想的，如果w的各位不存在x，那么w可能是由幸運數相加得到，每次減去最小幸運數x
至于證明，我也講不明白，當時做的時候是舉例子推出來的，下面看這個詳細證明
詳細證明

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=5e5+8; int a[maxn]; int q,d; bool f(int x) {if(x<d)return 0;int ans=x;bool flag=0;while(ans){if(ans%10==d){flag=1;break;}ans/=10;}if(flag==1)return 1;if(f(x-d))return 1;return 0; } int main() {int t;cin>>t;while(t--){cin>>q>>d;for(int i=1;i<=q;i++){int x;cin>>x;if(f(x))cout<<"YES"<<endl;else cout<<"NO"<<endl;}}return 0;}

J CodeForces 1478F Nezzar and Nice Beatmap

K CodeForces 1477D Nezzar and Hidden Permutations

L CodeForces 1481B New Colony

題意：

從山頂有石頭滾下來，有n個山，山的高度分別是hi
如果hi >= hi+1 ，石頭就會滾到下一個山
如果hi < hi+1，石頭會停止滾動（停在hi），hi的高度會加一
問第k次滾石會停到什么位置，會不會滾出所有山？

題解：

本題按照題意直接暴力即可
循環k次，記錄每次石頭滾到的位置，如果石頭沒有停下來（說明所有的i都滿足a[i]>=a[i+1]），說明石頭滾出所有山，此時輸出-1

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=5e5+8; int a[maxn]; int main() {int t;cin>>t;while(t--){int n,k;cin>>n>>k;memset(a,0,sizeof(a));for(int i=1;i<=n;i++)cin>>a[i];int ans=0;while(ans!=k){int i;bool f=0;for(i=1;i<n;i++){if(a[i]>=a[i+1])continue;else {f=1;a[i]++;ans++;break;}}if(f==0){cout<<-1<<endl;break;}if(ans==k){cout<<i<<endl;break;}}}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的一起开心集训队第一周训练赛2021/3/14的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。