开学第3周（cf+训练）

whatdo / 2024-03-22 / 原文

训练赛

天梯赛训练 - Virtual Judge (vjudge.net)

题解：比较🍬的题，需要我们统计24小时内船只上一共有多少个不同国的人

相当于暴力思想，我们直接开一个map记录每个国人数情况，然后算一下时间状态，用双指针然后前面超过24小时的就直接记录个数减减即可

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a;
    }
    return ans;
}


struct G
{
    int t,k;
}a[N];
vector< int> b[N];
map<int,int> mp;
void solve()
{
    int n;
    cin>>n;
    int ans=0;
    int l=1;
    for(int i=1;i<=n;i++)
    {
        int t,k;
        cin>>t>>k;
        a[i]={t,k};
        for(int j=1;j<=k;j++)
        {
            int x;
            cin>>x;
            b[i].push_back(x);
            mp[x]++;
            if(mp[x]==1) ans++;
        }
        while (a[i].t-a[l].t>=86400) {
            for (auto x: b[l]) {
                mp[x]--;
                if (mp[x] == 0) ans--;
            }
            l++;
        }

        cout<<ans<<endl;
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

天梯赛训练 - Virtual Judge (vjudge.net)

洛谷p5657

题解：我们可以倒着去思考

看看规律我们可以发现，在n的次幂里有pow(2,n)个数，pow(2,n)/2 左边的数全是通过加0，右边的数是加一

所以我们从最后开始推断，k如果大于pow(2,n)/2 那么这一位就是加一，如果小于或者等于那就是加0 一位一位向上推

这里就需要更新这个k看看下面一个是由上面哪一个推出来的

画图发现

如果是右边就是pow(2,n)-1-k 就是上一个坐标位置如果在左边那就是原来的k不动

比如n==3,k==5 那么n==2的时候就是pow(2,3)-1-5==2 也就是上一个的坐标以此类推

记得开--int128 2的64太大

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a;
    }
    return ans;
}



void solve()
{
    int n,k;
    cin>>n>>k;
    string s;
    for(int i=n;i>=1;i--)
    {
        int x=((__int128)1<<i)-1;
        if(k>x/2)
        {
            s+='1';
            k=x-k;
        }
        else
        {
            s+='0';
        }
    }
    cout<<s<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}