寒假訓練第一天-Codeforces Round #501 (Div. 3)
前言：又到寒假了，依舊是被疫情困在家里的一天，還是希望自己不那么fw，和隊長約了一塊訓練，div3開始，先練練手速，畢竟忙著期末考試得有半個月沒怎么碰過鍵盤了，該賬號開學前會持續更新每日訓練題解，寒假目標：紫名，
題目鏈接
A-Points in Segments
題意：一個區間長為m，n 次詢問，每次詢問標記一段區間，問最后有多少區間沒有標記，該題可參考校門外的樹
題解：資料較小，暴力標記即可，時間復雜度O(nm)，下面直接粘代碼
bool book[110];
int32_t main()
{
int n, m, a, b, num = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a >> b;
for(int j = a; j <= b; j++)
book[j] = 1;
}
for(int i = 1; i <= m; i++)
if(book[i] == 0) num++;
cout << num << endl;
for(int i = 1; i <= m; i++)
{
if(book[i] == 0) cout << i << ' ';
}
return 0;
}
再粘一下差分的代碼（O(max(n, m))）
int a[110], s[110];
int32_t main()
{
ICO;
int n, m, l, r, num = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> l >> r;
a[l]++, a[r + 1]--;
}
for(int i = 1; i <= m; i++)
{
s[i] = s[i - 1] + a[i];
if(s[i] == 0) num++;
}
cout << num << endl;
for(int i = 1; i <= m; i++)
if(s[i] == 0) cout << i << ' ';
return 0;
}
B-Obtaining the String
題意：給你兩個字串s，t，移動s的字母（只能相鄰之間移動），移動多少次可使s成為t（不要求最小移動步數），題目限制移動步數不得超過e4，
題解：很明顯如果s如果能通過移動成為t，最大步數不會超過n^2，e4的限制就沒有意義了，題目不要求最少步數，即可通過暴力向后匹配未匹配到的s[i]，然后將匹配的字母交換到前面即可，
int a[30], b[30];
vector<int> res;
int32_t main()
{
ICO;
int n, book = 0;
string s, t;
cin >> n >> s >> t;
for(int i = 0; i < n; i++) //記錄包含字母的個數
{
a[s[i] - 'a']++;
b[t[i] - 'a']++;
}
for(int i = 0; i < 26; i++) //若包含字母不同，肯定不能匹配
{
if(a[i] != b[i])
{
cout << -1;
return 0;
}
}
for(int i = 0; i < n; i++)
{
if(s[i] != t[i]) //遇到不匹配的字母
{
int j = i + 1;
while(s[j] != t[i]) j++; //兩字串所含字母相同，則一定可以找到匹配的字母
j--;
while(j >= i) //將匹配到的字母交換到前面，并記錄交換路徑
{
swap(s[j], s[j + 1]);
res.push_back(j + 1);
j--;
}
}
}
cout << res.size() << endl;
for(int i = 0; i < res.size(); i++)
cout << res[i] << ' ';
return 0;
}
C-Songs Compression
題意：有n個檔案，記憶體限制為m，每個檔案可壓縮，現給你每個檔案壓縮前和壓縮后的記憶體，要壓縮一部分檔案使所有的檔案可以全部存盤，求最少壓縮檔案的數量，
題解：用陣列存盤一下壓縮檔案的記憶體差，然后排序，從差值最大的開始壓縮，直到可以全部存盤，注意資料范圍，
ll a[maxn], b[maxn], c[maxn];
int32_t main()
{
ICO;
ll n, m, res = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i] >> b[i];
c[i] = a[i] - b[i];
res += a[i];
}
sort(c + 1, c + 1 + n, greater<ll> ());
int num = 0;
for(int i = 1; i <= n; i++)
{
if(res <= m) break;
res -= c[i], num++;
}
if(res <= m) cout << num;
else cout << -1;
return 0;
}
D-Walking Between Houses
題意：有n個房子（編號1-n），你需要走k步然后走過的價值和為s，價值是你每走一步的起點和終點所在房間編號的差的絕對值，兩步之間不能處于同一房子內（價值為0），所以一步的價值∈[1, n - 1]，輸出1-k步自己所在房間的編號，
題解：這題是這場比賽我被卡時間最長的，讀完題發現題意清楚，思路也有，但是上手敲的時候發現其中有了諸多限制，比如你走i步就必須留下k - i的距離（要保證接下來的k - i步都有房子可走），最后所剩距離不夠一趟的時候的處理方法等等，說一下思路，在你保留k - i的時候，若所剩距離大于n - 1，則可以一步從頭到尾（從尾到頭），否則就走完該步可走的，最后的k - i步每步走1就好，
int32_t main()
{
ICO;
ll n, k, s;
cin >> n >> k >> s;
if((n - 1) * k < s || k > s) cout << "NO" << endl;
else
{
cout << "YES" << endl;
ll p, sum = 0, now = 1;
bool ok = 1;
for(int i = 1; i <= k; i++)
{
p = (s - sum) - (k - i); //p為當前可走價值 sum為已走價值
if(p == 1) //最后k - i步，每步走1，注意轉頭
{
int j = i;
while(j <= k)
{
while(j <= k && (++now) <= n)
{
cout << now << ' ';
j++;
}
now--;
while(j <= k && (--now) >= 1)
{
cout << now << ' ';
j++;
}
now++;
}
break;
}
if(p >= n) //可走價值大于一步最大價值時頭尾跳即可
{
if(ok) now = n;
else now = 1;
p = n - 1;
ok = !ok;
}
else
{
if(ok) now = 1 + p;
else now = n - p;
}
sum += p;
cout << now << ' ';
}
}
return 0;
}
E-Stars Drawing
題意：判斷所給矩陣是否可以拆成幾個單獨的星星，原矩陣的‘*’可被拆成的星星共用，即被拆成的完整的星星的并集等于原矩陣，
題解：使用二維差分，對所拆的星星進行覆寫，看覆寫后的圖案和原矩陣是否匹配，
const int maxn = 1e3 + 2;
char ch[maxn][maxn];
int l[maxn][maxn], r[maxn][maxn], up[maxn][maxn], down[maxn][maxn], res1[maxn][maxn], res2[maxn][maxn];
int res[maxn][maxn];
vector<pair<pair<int, int>, int> > v;
int32_t main()
{
ICO;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> ch[i][j];
if(ch[i][j] == '*')
{
if(ch[i][j - 1] == '*') l[i][j] = l[i][j - 1] + 1;
if(ch[i - 1][j] == '*') up[i][j] = up[i - 1][j] + 1;
}
}
}
for(int i = n; i >= 1;i--)
{
for(int j = m; j >= 1; j--)
{
if(ch[i][j] == '*')
{
if(ch[i + 1][j] == '*') down[i][j] = down[i + 1][j] + 1;
if(ch[i][j + 1] == '*') r[i][j] = r[i][j + 1] + 1;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
int minn = min(min(l[i][j], up[i][j]), min(r[i][j], down[i][j]));
if(minn)
{
pair<int, int> l;
pair<pair<int, int>, int> q;
l.first = i, l.second = j;
q.first = l, q.second = minn;
v.push_back(q);
res1[i][j - minn]++, res1[i][j + minn + 1]--;
res2[j][i - minn]++, res2[j][i + minn + 1]--;
}
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
res1[i][j] += res1[i][j - 1];
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
res2[i][j] += res2[i][j - 1];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
res[i][j] = res1[i][j] + res2[j][i];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(ch[i][j] == '*' && res[i][j] == 0)
{
cout << -1 << endl;
return 0;
}
}
}
int l = v.size();
cout << l << endl;
for(int i = 0; i < l; i++)
cout << v[i].first.first << ' ' << v[i].first.second << ' ' << v[i].second << endl;
return 0;
}
總結：長時間不敲代碼確實會生疏很多，D題當時被卡了太久，期待在以后的學習中提高自己，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/248171.html
標籤：其他
上一篇：Unity使用角色控制器實作第一視角基本功能_學習筆記
下一篇：（期望DP）【總結】期望DP