Codeforces Round 981 (Div. 3)ABCDE
A. Sakurako and Kosuke
藕是看樣例直接猜了結論??
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
//-1
//3
//5
//7
int t; cin>>t;
while(t--)
{
ll x; cin>>x;
cout<<(x%2!=0?"Kosuke":"Sakurako")<<"\n";
}
return 0;
}
B. Sakurako and Water
思路：按從是負數的里面小到大遍歷這條最長的主對角線，貢獻就是加上這個最小的。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e3 + 10;
int a[N][N];
array<int,3>b[250010];
bool cmp(array<int,3> a,array<int,3> b)
{
return a[0] < b[0];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
int cnt = 0;
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= n; j++)
{
cin>>a[i][j];
if(a[i][j] < 0)
{
b[++cnt] = {a[i][j],i,j};
}
}
}
sort(b+1,b+1+cnt,cmp);
ll ans = 0;
for(int i = 1;i <= cnt; i++)
{
auto [v,x,y] = b[i];
if(a[x][y] >= 0)continue;
ans += (-a[x][y]);
int tx = x-1,ty = y-1;
while(tx >= 1 && ty >= 1)
{
a[tx][ty] += (-a[x][y]);
tx--,ty--;
}
tx = x+1,ty = y+1;
while(tx <= n && ty <= n)
{
a[tx][ty] += (-a[x][y]);
tx++,ty++;
}
a[x][y] = 0;
}
cout<<ans<<"\n";
}
return 0;
}
C. Sakurako's Field Trip
思路：因為\(a_i\)只能和\(a_{n-i+1}\)交換，相當于我們只用看一半就好了。分別看交換和不交換的貢獻，如果交換后小那么就交換。最后看一樣的數的個數。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int n;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
int ans = 0;
int n1 = 0,n2 = 0;
for(int i = 2;i <= n/2; i++)
{
n1 = 0,n2 = 0;
//a[i-1] a[i] ... a[n-i+1] a[n-i+2]
if(a[i] == a[i-1])
n1++;
if(a[n-i+1] == a[n-i+2])//n-(i-1)+1 = n-i+2
n1++;
if(a[i] == a[n-i+1])
n2++;
if(a[i-1] == a[n-i+2])
n2++;
if(n2 < n1)
swap(a[i],a[n-i+1]);
}
for(int i = 1;i < n; i++)
if(a[i] == a[i+1])
ans++;
cout<<ans<<'\n';
}
return 0;
}
D. Kousuke's Assignment
思路：很容易想到前綴和，做完前綴和之后，用last記錄上一次成為答案的最右邊的坐標。注意0的情況直接取本身就好了。mp[i]表示i上一次出現的位置，如果mp[i]>=last說明不會重疊可以成為答案，更新last = i。因為0是一定可以的，mp[0]初始化為-1就好了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N],s[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
s[i] = s[i-1]+a[i];
// for(int i = 1;i <= n; i++)
// cout<<s[i]<<" ";
map<ll,int>mp;
int cnt = 0,last = -1;
mp[0] = -1;
for(int i = 1;i <= n; i++)
{
if(mp.count(s[i]))
{
if(mp[s[i]] >= last)
{
last = i;
cnt++;
}
}
mp[s[i]] = i;
}
cout<<cnt<<"\n";
}
return 0;
}
E. Sakurako, Kosuke, and the Permutation
題意：給你一個排列(\(1～n\))，這個排列被認為是簡單的需要滿足下面其中一個條件：
對于每一個\(i(1\le i\le n)\)
- \(p_i = i\)
- \(p_{p_i} = i\)
問你最少交換多少次使得這個排列是簡單的。
思路：置換環（求解數組排序元素間所需最小交換次數這類問題）
思想：置換環將每個元素指向其排序后應在的位置，最終首位相連形成一個環（若數字在最終位置，則其自身成環）
對于\(i\rightarrow p[i] \rightarrow p[p[i]] \rightarrow p[p[p[i]]] \rightarrow ... \rightarrow i\) 這樣子的會構成一個環。需要滿足條件的話，環的長度需要\(\ge 2\)。即，最后這個數列轉化為圖一定是若干個自環和若干個兩數環所組成的圖。
對于環長度\(\le 2\)的，要進行交換操作讓環長度變短。我們發現讓\(p[p[i]] = i\)比讓\(p[i] = i\)更優，為什么呢？
我們設\(mp[i]\)為數值為\(i\)的下標。以\(2,3,4,1\)為例：
\(mp[1] = 4\)，\(p[1] = 2\)，我們想讓\(p[p[1]] = 1\)即\(p[2] = 1\),那么\(p[mp[1]] = p[2]\)，即\(p[4] = 3\)
交換完一次之后變成了\(2,1,4,3\)。同時更新\(mp[1] = 2,mp[3] = 4\)
這樣必定可以一次修改兩個數，是優于\(p[i]\)改成\(i\)的，那么對于環長度為\(size\)的，交換次數為\(\lfloor\dfrac{size-1}{2} \rfloor\)。
#include <bits/stdc++.h>
using namespace std;
struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n + 1);
std::iota(f.begin(), f.end(), 0);
siz.assign(n + 1, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
int main()
{
int t; cin>>t;
while(t--)
{
int n; cin>>n;
DSU d(n);
for(int i = 1;i <= n; i++)
{
int x; cin>>x;
d.merge(i,x);
}
set<int>s;
for(int i = 1;i <= n; i++){
d.f[i] = d.find(i);
s.insert(d.f[i]);
}
int ans = 0;
for(auto x : s)
{
ans += (d.siz[x]-1)/2;
}
cout<<ans<<"\n";
}
return 0;
}
或者直接模擬上述過程也是可以的：
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
map<int,int>mp;
vector<int>p(n+1);
for(int i = 1;i <= n; i++){
cin>>p[i];
mp[p[i]] = i;
}
int ans = 0;
for(int i = 1;i <= n; i++)
{
if(p[i] == i || p[p[i]] == i)
continue;
int s = mp[i],t = p[i];
swap(p[s],p[t]);
mp[p[s]] = s;
mp[p[t]] = t;
ans++;
}
cout<<ans<<"\n";
}
return 0;
}
//2 3 4 1
//2 1 4 3
//2 3 4 5 1
//2 1 4 5 3
//2 1 4 3 5
浙公網安備 33010602011771號