Codeforces Global Round 15

Codeforces Global Round 15

A - Subsequence Permutation

思路：找出原串与排序后的串不同的个数

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    string t=s;
    sort(t.begin(),t.end());
    int ans=0;
    for(int i=0;i<n;++i){
        ans+=(t[i]!=s[i]);
    }
    cout<<ans<<'\n';
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    
    return 0;
}

B - Running for Gold

思路：要找出一个人比所有人都好，依次比较所有人，找出一个最好的，再检查此人是否比其他人都好

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector a(n, vector<int>(5));
    for (auto &i: a)
        for (auto &j: i)
            cin >> j;
    int t = 0;
    for (int i = 1, f; i < n; i++) {
        f = 0;
        for (int j = 0; j < 5; j++)
            f += (a[i][j] < a[t][j]);
        if (f >= 3) t = i;
    }
    int cnt = 0;
    for (int i = 0, f; i < n; i++) {
        if (i == t) continue;
        f = 0;
        for (int j = 0; j < 5; j++)
            f += (a[i][j] > a[t][j]);
        if (f >= 3) cnt++;
        else break;
    }
    if (cnt == n - 1) cout << t+1 << "\n";
    else cout << "-1\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C - Maximize the Intersections

思路：对于初始没有弦的2n个点，可知连接1——1+n，2——2+n，...，n——n+n后的交点最多（弦的两边点的数量相同，弦与弦的较点更多）；

那么忽略已定的点，剩余的点一定有偶数个，为1~2（n-k），连接1——1+n-k，2——2+n-k，...，n-k——2（n-k）后的图即为最优情况；

枚举所有两条边的情况，分别为x1、y1，x2、y2，当x1<x2时，满足x2<y1和y1<y2即满足两条边相交

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=200+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

vector<PII>g;
vector<int>st,f;
void solve(){
    g.clear();
    f.clear();
    st=vector<int>(N,0);
    int n,k;cin>>n>>k;
    for(int i=0,u,v;i<k;++i){
        cin>>u>>v;
        if(u>v)swap(u,v);
        g.push_back({u,v});
        st[u]=st[v]=1;
    }
    for(int i=1;i<=2*n;++i){
        if(!st[i])f.push_back(i);
    }
    for(int i=0;i<n-k;++i){
        g.push_back({f[i],f[i+n-k]});
    }
    int ans=0;
    auto check=[](PII x,PII y){
        if(x.first>y.first)swap(x,y);
        return x.second<y.second&&y.first<x.second;
    };
    for(int i=0;i<n-1;++i)
        for(int j=i+1;j<n;++j){
            ans+=check(g[i],g[j]);
        }
    cout<<ans<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D - Array Differentiation

思路：要构造一个数组b，满足ai=bj-bk；设a₁=b₁-b₂，那么a₂=b₂-b₃，...，a_n-1=b_n-1-b_n，还有一个an没有得出；

假设an=bn-b1，那么可以将b看作点，a看作边权，要得到所有的a，说明要有环，且有环的情况下：a1+a2+...+an=（b1-b2）+（b2-b3）+...+（bn-b1）=0；

由于边为有向边，且n<=10，可以用三进制表示出每条边的情况，判断是否有环；

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=200+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int n,m=1;cin>>n;
    vector<int>a(n);
    for(auto &v:a)cin>>v,m*=3;
    for(int i=1;i<m;++i){
        int now=i,sum=0;
        for(int j=0;j<n;++j){
            if(now%3==1)sum+=a[j];
            else if(now%3==2)sum-=a[j];
            now/=3;
        }
        if(!sum){
            cout<<"YES\n";return;
        }
    }
    cout<<"NO\n";
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}