首页 > 其他分享 >iwtgm-34

iwtgm-34

时间:2023-12-12 18:45:43浏览次数:26  
标签:ch int void cin long iwtgm 线性 34

Educational Codeforces Round 159 (Rated for Div. 2)

A.

只要有0就是yes
因为若只有0,显然满足条件
若0和1都有,一定会有01相邻的情况,我们插入0后,仍有01相邻的情况,即我们可以无限+0,那么最后0的个数一定可以大于1

void solve() {
    int n;cin>>n;
    string s;cin>>s;
    int cnt_0=0,cnt_1=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0')cnt_0++;
        else cnt_1++;
    }
    if(cnt_0&&cnt_1||cnt_0){
        cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;
}

B.

这种题思路容易出,但代码实现还是有点东西

#define int long long
void solve() {
    int n, P, l, t;
    cin >> n >> P >> l >> t;
    int x = (n + 6) / 7;
    // debug1(x);
    int s = (x / 2) * (l + t * 2);
    int ss = s + (x % 2) * (l + t);
    int d = (l + t * 2);
    if(s >= P){
        cout << n - (P + d - 1) / d << endl;
    }
    else if(ss >= P){
        cout << n - (x + 1) / 2 << endl;
    }
    else {
        P -= ss;
        int ans = (x + 1) / 2 + (P + l - 1) / l;
        cout << n - ans << endl;
    }
}

C.

想错的点是a(n+1)可以比a(n)小

#define int long long
 
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    set<int> st;
    for(auto &i : a) {
        cin >> i;
        st.insert(i);
    }
    vector<int> ans;
    sort(a.begin(), a.end());
    int mx = a.back();
    for(auto i : a) {
        if(mx - i != 0)
            ans.push_back(mx - i);
    }
    if(!ans.size()) {
        cout << 1 << endl;
        return ;
    }
    int gc = ans[0];
    for(int i = 1; i < ans.size(); i++) {
        gc = __gcd(gc, ans[i]);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) {
        if(!st.count(mx - gc * i)) {
            res = i;
            break;
        }
    }
    if(res == 0)res = n;
    for(auto i : ans) {
        res += i / gc;
    }
    cout << res << endl;
}

D.

思路一直绕在点中心转换,其实不用
就按它题意,算偏移量,然后去二分查找是否存在

#define x first
#define y second
#define pt pair<int,int>
 
void solve() {
    int n,q;cin>>n>>q;
    string s;cin>>s;
    vector<pt>pos(n+1);
    for(int i=0;i<n;i++){
        pos[i+1].x=pos[i].x+(s[i]=='R')-(s[i]=='L');
        pos[i+1].y=pos[i].y+(s[i]=='U')-(s[i]=='D');
    }
    map<pt,vector<int>>mp;
    for(int i=0;i<=n;i++)mp[pos[i]].push_back(i);
    auto check=[&](pt p,int l,int r){
        if(!mp.count(p))return false;
        auto it= lower_bound(mp[p].begin(),mp[p].end(),l);
        return it!=mp[p].end()&&*it<=r;
    };
    while(q--){
        int x,y,l,r;cin>>x>>y>>l>>r;
        int nx=pos[r].x+pos[l-1].x-x,ny=pos[r].y+pos[l-1].y-y;
        bool f=check({x,y},0,l-1)|check({nx,ny},l,r-1)|check({x,y},r,n);
        cout<<(f?"YES":"NO")<<endl;
    }
}

E.

用字典树就可以很好地解决了

using ll = long long;
using pii = pair<int, int>;
using vint = vector<int>;
using vpo = vector<pii>;
 
vector<string> s(1000006);
int trie[1000006][26],cnt[1000006][26], tot = 0;
void insert(string str) {
    int p = 0;
    for (auto& c : str) {
        int ch = c - 'a';
        if (trie[p][ch] == 0)trie[p][ch] = ++tot;
        ++cnt[p][ch];
        p = trie[p][ch];
    }
}
ll que(string str) {
    int p = 0; ll ret = 0;
    for (int i = str.size() - 1; i >= 0; i--) {
        int ch = str[i] - 'a';
        ret += cnt[p][ch];
        p = trie[p][ch];
        if (p == 0)break;
    }
    ll size = str.size();
    return ret;
}
int main(void)
{
    IOS;
    int n; cin >> n;
    ll sumlen = 0;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        insert(s[i]);
        sumlen += s[i].size();
    }
    ll ans=sumlen* 2 * n;
    for (int i = 1; i <= n; i++) {
        ans -= que(s[i])*2;
    }
    cout << ans << endl;
}

F.
浅学下异或线性基
异或性质:
若a\(\bigoplus\)b\(\bigoplus\)c=0,则a\(\bigoplus\)b=c
若a\(\bigoplus\)b=c,则a\(\bigoplus\)c=b

异或线性基:若集合a中的每一个数都能用集合b中的若干个(可为0个)数按位异或得出,
且集合b是满足上述要求的元素个数最少的集合,那么称b是a的一个异或线性基

a[]储存所有的线性基
a[i]表示线性基中(先出现的)最高位为i的元素(唯一,就是说这一位为1就标志着这个数,其他数都被抵消)(后面的这一位会被抵消,后面会再说)
如果a[i]=0,表示线性基里还没有最高位为第i位的元素
将元素x插入线性基里,从高到低枚举x的每一个二进制位
假设枚举到第i位
如果a[i]=0,那就说明x的第i位不能被目前线性基里的数异或出,所以必须把x插入线性基,即a[i]=x;
否则,我们要把x的第i位用a[i]消掉,也就是x^a[i].(这就是为什么我们要让线性基内任意两个数的二进制最高位不同,因为这样才能起到消位的作用)

#define int long long
int n;
int a[51];
void get_lb(int x){
    for(int i=50;i>=0;i--){
        if((x&(1ll<<i))==0)continue;
        if(a[i]>0)x^=a[i];
        else{
            a[i]=x;
            return ;
        }
    }
}
void solve() {
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        get_lb(k);
    }
}

标签:ch,int,void,cin,long,iwtgm,线性,34
From: https://www.cnblogs.com/wwww-/p/17897574.html

相关文章

  • ACwing343.排序
    1.Floyd写法:#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintN=26;intn,m;boold[N][N];boolst[N];intcheck(){for(inti=0;i<n;i++)if(d[i][i])re......
  • P2341 受欢迎的牛 G 题解
    LinkP2341[USACO03FALL/HAOI2006]受欢迎的牛GQuestion牛栏中有\(N\)头奶牛,和一些\(M\)对爱慕关系,A->B表示A爱慕B。每个奶牛都喜欢自己,被所有奶牛喜欢就是一头明星奶牛,求明星奶牛的数量Solution考虑一个强连通分量里面的奶牛是相互爱慕的,先根据强连通分量缩点,缩......
  • 234. 回文链表
    题目介绍给你一个单链表的头节点\(head\),请你判断该链表是否为回文链表。如果是,返回\(true\);否则,返回\(false\)。示例1:输入:head=[1,2,2,1]输出:true示例2:输入:head=[1,2]输出:false提示:链表中节点数目在范围\([1,10^{5}]\)内\(0<=Node.val<=9\)进......
  • 代码随想录算法训练营第7天 | lc344、lc541、卡码54、lc151、卡码55
    (本合集全部为Go语言实现)相关文章链接:344题解541题解卡码54题解151题解卡码55题解相关视频链接:Leetcode344状态:秒了实现过程中的难点:对撞双指针个人写法funcreverseString(s[]byte){fori,j:=0,len(s)-1;i<j;i,j=i+1,j-1{s[i],s[j]......
  • 1234435
    我觉得这道题目如果只有第一个问题的话,排序方式是多种多样的,而且考虑的对象也可以是机器比如我可以给机器按照\(y\)从小到大排序,然后依次考虑每个机器,对于每个机器,在能选择的任务中选择\(x\)最大的即可但这个时候就没有办法保证价值最大了,所以这道题启发我们,如果一道题目有多维......
  • 代码随想录算法训练营第七天| 344.反转字符串 541. 反转字符串II
    LeetCode344.反转字符串题目链接: LeetCode344思路: 定义left、right指针,将两指针对应的值反转即可 classSolution{public:voidreverseString(vector<char>&s){intn=s.size();for(intleft=0,right=n-1;left<right;++left,--right){......
  • skywalking 部署安装 https://blog.csdn.net/swg321321/article/details/129704345
    https://blog.csdn.net/swg321321/article/details/129704345 前言在分布式系统中会出现服务间的相互调用,且服务数量众多。一般会出现如下异常请求出现异常,需要定位定位具体是哪个服务器发生异常,需要对这个请求链路一步一步调试才能确定那个服务出现异常。出现定位异常服务难......
  • iwtgm-33
    CodeforcesRound912(Div.2)A.只要k大等于2,那么每个数的位置就可以任意放置(两两交换可以到达任何位置),一定可以符合条件特判序列本来就升序,那么k的值无关紧要intn,k;inta[110];voidsolve(){cin>>n>>k;boolflag=true;for(inti=1;i<=n;i++){c......
  • [LeetCode Hot 100] LeetCode234. 回文链表
    题目描述思路1:将值复制到数组中然后使用双指针计算链表的长度创建等长的数组将链表中的数依次放入数组中使用左右指针判断链表是否是回文链表时间复杂度:O(n)空间复杂度:O(n)思路2:快慢指针+反转链表用快慢指针,快指针走两步,慢指针走一步,快指针遇到终止位置时,慢指针就在......
  • ACwing342. 道路与航线
    这道题是把拓扑排序和迪杰斯特拉交叉进行。#include<iostream>#include<stdio.h>#include<algorithm>#include<cstring>#include<queue>#include<vector>usingnamespacestd;typedefpair<int,int>PII;constintN=25005,M=50......