首页 > 其他分享 >cf 918(D-G) div4

cf 918(D-G) div4

时间:2023-12-31 15:44:46浏览次数:34  
标签:10 int ll cf long 918 端点 div4 逆序

cf 918(D-G)div4

D.Unnatural Language Processing

算法分析:string模拟+贪心

贪心策略:把元音字母看作0,辅音字母作为1,因为是等价的,构造字符串,寻找a.find("101"),a.find("10");判断合理性,贪心选择101还是10,最后把原数组打印,erase删除前面的"101"/"10"串,直到串删为空

不要偷懒递归,会爆内存,博主就是偷懒的

#include<bits/stdc++.h>
using namespace std;
int t;
typedef long long ll;
#define str  string
 int n;
void ustr(str a, str b)
{
 
    while(1)
    {
        int pose = b.find("10");
    int npose = b.find("101");
    if (npose > 0)
    {
        if (b.size() > 2)
            cout << a.substr(0, 2) << '.';
        else
            {cout << a.substr(0, 2)<<endl;break;}
        a.erase(0,2);
        b.erase(0,2);
    }
    else
    {
        if (b.size() > 3)
        {
            if (b[3] == '0')
            {
                if (b.size() > 2)
                    cout << a.substr(0, 2) << '.';
                else
                    {
                        cout << a.substr(0, 2) << endl;
                        break;
                    }
             a.erase(0,2);
        b.erase(0,2);
            }
            else
            {
                cout << a.substr(0, 3) << '.';
                b.erase(0,3);
                a.erase(0,3);
            }
        }
        else
            {
                cout << a << endl;
                break;
            }
      }
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    cin >> t;
    while (t--)
    {
        cin >> n;
        string a, b;
        cin >> a;
        b = a;
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 'a' || a[i] == 'e')b[i] = '0';
            else b[i] = '1';
        }
        ustr(a, b);
    }
   return 0;
  }

E.Romantic Glasses

算法分析:set判断+贪心策略

将奇数项和偶数项分别作为整数和负数

当出现一段大小不变说明可以产生连续相等串(res+=a[i];set.insert(res);

也就是后面一段存在和为0的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
ll a[200020];
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i+=2)a[i]=-a[i];
  set<ll>s;
  s.insert(0);
  ll res=0;
  bool df=false;
  for(int i=1;i<=n;i++)
  {
   res+=a[i];
   if(s.count(res))
   {
    cout<<"YES\n";df=true;
    break;
   }
   s.insert(res);
  }
  if(!df)
  cout<<"NO\n";
}
    return 0;
}

F.Greetings

观察贪心本题目实际是求包含(下面左端点x,右端点y)

也就是左端点L,右端点R

L1<=l2,R2<=R1;

我们很自然想到排序左端点

但是接下来如何求包含呢,一个神奇的东西出现了,y总算法基础课的求逆序对

788. 逆序对的数量 - AcWing题库

逆序对的定义如下::对于数列的第i个和第j个元素,如果满足i<j且a[i]>a[j],则其为一个逆序对;否则不是

如果我们将区间按照左端点排序,我们要求的其实就是后面的点(x排序后)且符合其y小于等于我们现在的右端点,我们只要小改逆序对定于为a[i].y>=a[j].y即可符合此题目

//ac代码
#include<bits/stdc++.h>
 using namespace std;
int t;
const int N=2e5+10;
int n;
typedef long long ll;
struct p{
    int x,y;
}a[N],tmp[N];
bool cmp(p c,p d)
{
   if(c.x==d.x)return c.y<d.y;
    return c.x<d.x;
}
ll my_sort(int l,int r)
{
    if(l>=r)return 0;
    int mid=(l+r)>>1;
    ll res=my_sort(l,mid)+my_sort(mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
   if(a[i].y<a[j].y)tmp[k++].y=a[i++].y;
    else
    {
        res+=mid-i+1;
        tmp[k++].y=a[j++].y;
    }
    while(i<=mid)tmp[k++].y=a[i++].y;
    while(j<=r)tmp[k++].y=a[j++].y;
    for(int i=l,j=0;i<=r;i++,j++)
  a[i].y=tmp[j].y;
  return res;
}
void sovle()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    int l=1,r=n;
    sort(a+1,a+1+n,cmp);
    cout<<my_sort(l,r)<<endl;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    cin>>t;
    while(t--)
    sovle();
    return 0;
}

G.Bicycles

算法分析:二维dijstra

请允许蒻蒟还不会吧,呜呜

标签:10,int,ll,cf,long,918,端点,div4,逆序
From: https://www.cnblogs.com/yuexiabaobei/p/17937565

相关文章

  • CF1916C Training Before the Olympiad
    思路首先,我们可以考虑两个人会怎么操作,如果是选择了两个偶数和两个奇数,那么答案不会减小,如果选择了一个奇数一个偶数,那么答案会减小一。所以想使答案大的人应该尽量选择前一种方案,想使答案小的人应该尽量选择后一种方案。但这还不是最优的,想使答案大的人在可以选择两个奇数时,绝......
  • CF1916D Mathematical Problem
    思路很不错的人类智慧题。拿到以后,完全没有思路,看到数据范围,感觉是什么\(n^2\logn\)的逆天做法,但是又完全没思路,看后面的题感觉没希望,就在这道题死磕。先打了个暴力程序,发现平方数太多,没什么规律,就拿了个map统计一下那些出现数字方案拥有的平方数比较多程序如下:#include......
  • CF1916B Two Divisors
    思路看到题目要求求一个数\(x\),满足它的最大的两个因数分别是\(a\)和\(b\),并且规定一个数本身不是他的因数。首先\(x\)需要是\(a\)和\(b\)的倍数,所以想到最小公倍数,如果不考虑最小公倍数等于\(b\),最小公倍数就一定是答案,因为最小公倍数是最小的满足是\(a\)和\(b\)......
  • CF121E Lucky Array
    题意给定一个序列,维护下列操作。区间加区间查询数中只包含\(4,7\)数的个数。所有数前后不超过\(1e4\)。Sol块块版。\(1e4\),发现满足条件的数的个数只有\(30\)个。对于每个块开一个桶,记录每种数有多少个。查询时暴力枚举\(30\)个数,暴力判断即可。修改是平凡的......
  • CF1795F Blocking Chips
    题意给定一棵大小为\(n\)的树,有\(k\)个人,第\(i\)个人在节点\(a_i\)。从第\(1\)秒开始,依次操作第\(1,2,3,\ldots,k,1,2,3,\ldots,k,\ldots,k,\ldots\)个人,把这个人移动到没有走过的点。Sol调了\(3h\),给哥们整吐了。不难想到二分答案时间,算出每个人走......
  • 「杂题乱刷」CF1916C
    题目传送门(CF)题目传送门(luogu)容易发现,选择两个偶数对于答案没有任何影响,因此先手必然会优先选择两个奇数合并在一起,而后手必然会优先选择一个奇数和一个偶数在一起,我们举个例子,有一个序列\(\{1,1,1,1,1,1\}\),先手先取编号为\(1,2\)的两个数,后手再取编号为\(2,3\)的两个数,此......
  • Codeforces Round 918 (Div. 4) (前缀和,权值树状数组,二维偏序, python + golang)
    Dashboard-CodeforcesRound918(Div.4)-Codeforces  fromcollectionsimport*defsolve():a,b,c=list(map(int,input().split()))hs=defaultdict(int)hs[a]+=1hs[b]+=1hs[c]+=1foriinhs:ifhs[i]=......
  • CF1254D Tree Queries
    TreeQueriesLuoguCF1254D题面翻译给定一棵\(N\)个节点的树,有\(Q\)次操作。\(1\v\d\)给定一个点\(v\)和一个权值\(d\),等概率地选择一个点\(r\),对每一个点\(u\),若\(v\)在\(u\)到\(r\)的路径上,则\(u\)的权值加上\(d\)(权值一开始为\(0\))。\(2\v\)查......
  • CF1320E Treeland and Viruses
    TreelandandVirusesLuoguCF1320E题面翻译有一棵有\(n\)个节点的树,\(q\)次询问(询问互相独立),每次给定\(k_i\)个颜色,每个颜色有一个起始点\(v_j\)和移动速度\(s_j\),每一个颜色在每一次操作中会使它周围没有被染色的连通块上与它的距离不超过\(s_j\)的点全部染为这一......
  • [Codeforces] CF1545A AquaMoon and Strange Sort
    CF1545AAquaMoonandStrangeSort题目传送门题意有\(n\)个人从左到右站成一排,从左数第\(i\)个人的衣服上印着\(a_i\)。每个人的朝向可以是朝左、朝右。一开始所有人的方向都是朝右。您可以对这些人做一些“操作”,每次操作允许您找两个相邻的人让他们交换顺序,但是在操作......