《Codeforces Global Round 16》

2024-02-25 18:32:45

A：

《Codeforces Global Round 16》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

void solve() { 
    int n,s;n = read(),s = read();
        int hf = n / 2 + 1;
        int ans = s / hf;
        printf("%d\n",ans);
} 
int main() {    
    int ca;ca = read();
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}
View Code

B：

《Codeforces Global Round 16》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

void solve() { 
    string s;cin >> s;
    int len = 0,ans = 0;
    for(auto v : s) {
        if(v == '1') {
            if(len != 0) ans++;
            len = 0;
        }
        else len++;
    }
    if(len != 0) ans++;
    ans = min(ans,2);
    printf("%d\n",ans);
} 
int main() {    
    int ca;ca = read();
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}
View Code

C：

《Codeforces Global Round 16》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

void solve() {
    int n;n = read();
    string a,b;
    cin >> a >> b;
    int f0 = 0,f1 = 0;
    int ans = 0;
    for(auto v : a) {
        if(v - '0' == 0) f0 = 1;
        else f1 = 1;
    }
    for(auto v : b) {
        if(v - '0' == 0) f0 = 1;
        else f1 = 1;
    }
    for(int i = 0;i < n;++i) {
        if(a[i] == '0' && b[i] == '1' || a[i] == '1' && b[i] == '0') ans += 2;
        else if(a[i] == '0' && b[i] == '0') {
            if(i == n - 1) ans += 1;
            else {
                if(a[i + 1] == '1' && b[i + 1] == '1') ans += 2,++i;
                else ans++;
            }
        }
        else if(a[i] == '1' && b[i] == '1') {
            if(i < n - 1 && a[i + 1] == '0' && b[i + 1] == '0') ans += 2,++i;
        }
    }
    if(f1 == 1 && f0 == 1) ans = max(ans,2);
    printf("%d\n",ans);
}
int main() {
    int ca;ca = read();
    while(ca--) {
        solve();
    }
    return 0;
}
View Code

D1：因为只有一行，所以排序后的位置就是他们固定的位置。

比较特殊的地方就是连续相同的处理，很显然我们先放位置最后面的更优。

《Codeforces Global Round 16》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

int a[N];
vector<int> vec;
void solve() {
    vec.clear();
    int n,m;n = read(),m = read();
    for(int i = 1;i <= n * m;++i) a[i] = read();
    LL ans = 0;
    for(int i = 1;i <= n * m;++i) {
        if(vec.size() == 0) ans += 0;
        else {
            int pos = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin();
            if(pos != 0) ans += pos;
        }
        vec.push_back(a[i]);
        sort(vec.begin(),vec.end());
    }
    printf("%lld\n",ans);


}
int main() {
    int ca;ca = read();
    while(ca--) {
        solve();
    }
    return 0;
}
View Code

D2：也是类似的，这里只有一点不同，那就是对于连续的位置，我们先放位置最前面的更优。因为这样可以保证其他的前面的包含的尽量少。

线段树查询一下就行。这里写的树状数组

《Codeforces Global Round 16》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

int a[N],b[N],c[N],tot[N],sum[N],n,m;
vector<int> vec[N];
int lowbit(int x) {return x & (-x);}
void add(int x) {
    for(int i = x;i <= n * m;i += lowbit(i)) sum[i]++;
}
int query(int x) {
    int ans = 0;
    for(int i = x;i;i -= lowbit(i)) ans += sum[i];
    return ans;
}
int query2(int L,int r) {
    return query(r) - query(L - 1);
}
int cal(int pos) {
    int L;
    if(pos % m == 0) L = pos / m - 1;
    else L = pos / m;
    return L;
}
void solve() {
    n = read(),m = read();
    for(int i = 1;i <= n * m;++i) a[i] = read(),b[i] = a[i],sum[i] = 0,c[i] = a[i];
    sort(c + 1,c + n * m + 1);
    sort(b + 1,b + n * m + 1);
    int len = unique(b + 1,b + n * m + 1) - b - 1;
    for(int i = 1;i <= len;++i) vec[i].clear(),tot[i] = 0;
    LL ans = 0;
    for(int i = 1;i <= n * m;++i) {
        int x = lower_bound(b + 1,b + len + 1,c[i]) - b;
        vec[x].push_back(i);
    }
    for(int i = 1;i <= n * m;++i) {
        int x = lower_bound(b + 1,b + len + 1,a[i]) - b;
        int pos = vec[x][tot[x]++],L;
        int c1 = cal(pos);
        int c2 = cal(vec[x][0]);
        if(c1 == c2) {
            int L = c2 * m + 1;
            if(vec[x][0] > L) ans += query2(L,vec[x][0] - 1);
        }
        add(pos);
    }
    printf("%lld\n",ans);
}
int main() {
    int ca;ca = read();
    while(ca--) {
        solve();
    }
    return 0;
}
View Code

E：一开始想的挺对的，不管怎么拼接，bud的拆除方式都不会改变。

那么每个bud的贡献就是leaves - 1.

但是我一开始只考虑到了初始是bud的情况，但是在删去一些bud之后会出现新的bud，这也要算上。

《Codeforces Global Round 16》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

vector<int> G[N];
int ans;
int dfs(int u,int fa) {
    int sum = 0;
    for(auto v : G[u]) {
        if(v == fa) continue;
        sum += dfs(v,u);
    }
    if(sum == 0) return 1;//一开始是叶子或者子节点被删完
    else {
        ans += sum - 1;
        return 0;
    }
}
void solve() {
    int n;n = read();
    for(int i = 1;i <= n;++i) G[i].clear();
    ans = 0;
    for(int i = 1;i < n;++i) {
        int u,v;u = read(),v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    printf("%d\n",ans + 1);
}
int main() {
    int ca;ca = read();
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}
View Code

F：一开始理解错题意了。这题是只要碰到线段上的某个点就算到过了。

然后就有两种情况：

1：线段上本来就有点，那就可以删去这条线段。

2：线段里有更小的线段（完全包含）。那大的可以删掉，因为到小的大的也肯定到，到大的小的不一定到。

然后现在就是一种关于点和线段的排列p1 [L1,r1] [L2,r2] ...p2 ....p3..

考虑dp[i][0] - 点i移动完前面所有点后回到原位的最小步数。dp[i][1] - 不回到原位。

转移：对于不回到原的点，我们不能知道它在哪个位置，但是我们可以看成(处理完右边回到原位) + 不回到原位的代价 = 在原位向左不回到原位。

struct用long long就T了。需要用int

《Codeforces Global Round 16》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

LL a[N];
struct Node{int L,r;};
LL dp[N][2],vecL[N],vecr[N];//0 - 回到原位置,1 - 不回到原位置.
bool cmp(Node a,Node b) {
    if(a.L != b.L) return a.L < b.L;
    else return a.r > b.r;
}
vector<Node> v;
void solve() {
    int n,m;n = read(),m = read();
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    sort(a + 1,a + n + 1);
    v.clear();
    for(int i = 1;i <= m;++i) {
        int L,r;L = read(),r = read();
        int pos = lower_bound(a + 1,a + n + 1,L) - a;
        if(pos == n + 1 || a[pos] > r) v.push_back(Node{L,r});
    }
    sort(v.begin(),v.end(),cmp);
    for(int i = 0;i < v.size();++i) {
        if(i != 0 && v[i].r <= v[i - 1].r) {
            v.erase(v.begin() + i - 1);
            i -= 2;
        }
    }
    int now = 0;
    for(int i = 1;i <= n + 1;++i) dp[i][0] = dp[i][1] = INF;
    dp[0][0] = dp[0][1] = 0;
    a[0] = -1e18;
    a[n + 1] = 1e18;
    for(int i = 1;i <= n + 1;++i) {
        int cnt0 = 0,cnt1 = 0;
        vecL[++cnt0] = a[i - 1];
        while(now < v.size() && v[now].r < a[i]) {
            vecL[++cnt0] = v[now].L;
            vecr[++cnt1] = v[now++].r;
        }
        vecr[++cnt1] = a[i];
        for(int j = 1;j <= cnt0;++j) {
            dp[i][0] = min(dp[i][0],dp[i - 1][0] + (vecL[j] - a[i - 1]) + 2LL * (a[i] - vecr[j]));
            dp[i][1] = min(dp[i][1],dp[i - 1][0] + (vecL[j] - a[i - 1]) + (a[i] - vecr[j]));
            dp[i][0] = min(dp[i][0],dp[i - 1][1] + 2LL * (vecL[j] - a[i - 1]) + 2LL * (a[i] - vecr[j]));
            dp[i][1] = min(dp[i][1],dp[i - 1][1] + 2LL * (vecL[j] - a[i - 1]) + (a[i] - vecr[j]));
        }
      //  printf("dp[%d][0] is %lld dp[%d][1] is %lld\n",i,dp[i][0],i,dp[i][1]);
    }
    printf("%lld\n",min(dp[n + 1][0],dp[n + 1][1]));
}
int main() {
    int ca;ca = read();
    while(ca--) {
        solve();
    }
  //  system("pause");
    return 0;
}
View Code

 

上一篇：c++一些记录


下一篇：使用group by对数据进行汇总计算