首页 > 其他分享 >Codeforces Round 982 (Div. 2)(A~C)

Codeforces Round 982 (Div. 2)(A~C)

时间:2024-11-07 19:18:57浏览次数:1  
标签:le 982 ll Codeforces 数组 ans Div include mod

对dp还不是特别熟练
只做到了C(还是太菜了),开始前刚好各种事情来了,vp晚了10多分钟开才始做题,喜提排名(不是)3000+,后面有时间就尽量把dp补掉

A. Rectangle Arrangement

你需要在一个无限的方格网格上涂色,所有格子最初都是白色的。为了完成这项任务,你有 \(n\) 个印章。每个印章是一个宽度为 \(w_i\)、高度为 \(h_i\) 的矩形。
你将使用 每个 印章 恰好一次 在网格上涂一个与印章同样大小的矩形区域为黑色。你不能旋转印章,对于每个格子,印章必须完全覆盖它或者完全不覆盖它。你可以在网格上的任何位置使用印章,即使印章覆盖的一些或全部格子已经是黑色的。
在使用完所有印章之后,你能得到的黑色方格区域的 周长之和 的最小值是多少?
\(Input\)
每个测试包含多个测试案例。第一行包含测试案例的数量 t(1≤t≤500)。每个测试案例的描述紧随其后。
每个测试案例的第一行包含一个整数 n(1≤n≤100)。
接下来的 n 行中,第 i 行包含两个整数 wi 和 hi(1≤wi,hi≤100),分别代表第 i 个印章的宽度和高度。
\(Output\)
对于每个测试案例,输出一个整数——在使用完所有印章后,你能得到的黑色方格区域周长之和的最小值。
\(Sample\)
5
5
1 5
2 4
3 3
4 2
5 1
3
2 2
1 1
1 2
1
3 2
3
100 100
100 100
100 100
4
1 4
2 3
1 5
3 2


20
8
10
400
16
思路:这题我是老老实实进行了区域覆盖,然后dfs了一遍区域,看周长
没想到是小学数学,\(2*max(h)*max(w)\),也确实是啊,vp时真是脑子抽了

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll                                     long long
#define lowbit(x) (x & -x)
//#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
ll ksm(ll x, ll y)
{
ll ans = 1;
while (y)
{
if (y & 1)
{
ans = ans % mod * (x % mod) % mod;
}
x = x % mod * (x % mod) % mod;
y >>= 1;
}
return ans % mod % mod;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct s
{
    ll x,y;
}p[2500];
ll a[400][400];
ll d[4]={0,1,-1,0};
ll e[4]={1,0,0,-1};
int main()
{
    fio();
    ll t;
    cin>>t;
    while(t--)
    {
        for(ll i=1;i<=100;i++)
        {
            for(ll j=1;j<=100;j++)
            a[i][j]=0;
        }
        ll n;
        cin>>n;
        for(ll i=1;i<=n;i++)
        {
            ll w,h;
            cin>>w>>h;
            for(ll k=1;k<=w;k++)
            {
                for(ll u=1;u<=h;u++)
                {
                    a[k][u]=1;
                }
            }
        }
        ll ans=0;
        for(ll i=0;i<=101;i++)
        {
            for(ll j=0;j<=101;j++)
            {
             for(ll u=0;u<=3;u++)
             {
                ll nx=i+d[u];
                ll ny=j+e[u];
                if(nx>=1&&nx<=100&&ny>=1&&ny<=100&&a[i][j]==0)
                {
                    if(a[nx][ny])ans++;
                }
             }   
            }
        }
        cout<<ans<<endl;
    }
}

B. Stalin Sort

斯大林排序(Stalin Sort)是一种幽默的排序算法,它不是为了正确地对元素进行排序,而是为了消除那些不在适当位置的元素,从而实现 \(\mathcal{O}(n)\) 的时间复杂度。
斯大林排序的步骤如下:从数组的第二个元素开始,如果它严格小于前一个元素(忽略那些已经被删除的元素),那么就删除它。继续遍历数组,直到数组按照非递减顺序排序。例如,数组 \([1, 4, 2, 3, 6, 5, 5, 7, 7]\) 在经过斯大林排序后变为 \([1, 4, 6, 7, 7]\)。
我们定义一个数组为“易受攻击”的,如果你可以通过反复对它的任意子数组应用斯大林排序,无论需要多少次,来将其排序成非递增顺序。
给定一个包含 \(n\) 个整数的数组 \(a\),确定必须从数组中移除的最小整数数量,以使其变得“易受攻击”。
\(^{\text{∗}}\) 如果数组 \(a\) 可以通过从数组 \(b\) 删除若干(可能为零或全部)开头和结尾的元素来获得,那么数组 \(a\) 就是数组 \(b\) 的一个子数组。
\(Input\)
每个测试包含多个测试案例。第一行包含一个整数 \(t\)(\(1 \le t \le 500\))——测试案例的数量。之后是测试案例的描述。
每个测试案例的第一行包含一个整数 \(n\)(\(1 \le n \le 2000\))——数组的大小。
每个测试案例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)(\(1 \le a_i \le 10^9\))。
保证所有测试案例中 \(n\) 的总和不超过 \(2000\)。
\(Output\)
对于每个测试案例,输出一个整数——必须从数组中移除的最小整数数量,以使其变得“易受攻击”。
\(Sample\)
6
7
3 6 4 9 2 5 2
5
5 4 4 2 2
8
2 2 4 4 6 6 10 10
1
1000
9
6 8 9 10 12 9 7 5 4
7
300000000 600000000 400000000 900000000 200000000 400000000 200000000


2
0
6
0
4
2
样例解析:
在第一个测试案例中,最优解是移除数字 \(3\) 和 \(9\)。这样我们剩下的数组为 \(a = [6, 4, 2, 5, 2]\)。为了证明这个数组是“易受攻击”的,我们可以先对子数组 \([4, 2, 5]\) 应用斯大林排序,得到 \(a = [6, 4, 5, 2]\),然后对子数组 \([6, 4, 5]\) 应用斯大林排序,得到 \(a = [6, 2]\),这是一个非递增序列。
在第二个测试案例中,数组已经是非递增的,所以我们不需要移除任何整数。
思路:说了这么多,其实题意等价于问第一个是不是最大的数,枚举每一个数作为第一个,前面的要全删除,然后后面比这个数大的也要删除,这样子就可以保证排序到最后可以获得不递增的排列
不妨象想想,第一个数非最大数,且后面有更大数时是无解的

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll                                     long long
#define lowbit(x) (x & -x)
//#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
ll ksm(ll x, ll y)
{
ll ans = 1;
while (y)
{
if (y & 1)
{
ans = ans % mod * (x % mod) % mod;
}
x = x % mod * (x % mod) % mod;
y >>= 1;
}
return ans % mod % mod;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[4500];
int main()
{
    fio();
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        for(ll i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        ll ans=9999999999;
        for(ll i=1;i<=n;i++)
        {
            ll cnt=i-1;
          for(ll j=i+1;j<=n;j++)
          {
            if(a[j]==a[i])continue;
            else if(a[j]>a[i])cnt++;
          }
          ans=min(ans,cnt);
        }
        cout<<ans<<endl;
    }
}

C. Add Zeros

您将获得一个最初包含 \(n\) 个整数的数组 \(a\)。在一个操作中,您必须执行以下操作:
选择一个位置 \(i\),使得 \(1 < i \leq |a|\) 且 \(a_i = |a| + 1 - i\),其中 \(|a|\) 是数组的当前大小。
在 \(a\) 的末尾追加 \(i - 1\) 个零。
在您想要多次执行此操作后,数组 \(a\) 的最大可能长度是多少?
\(Input\)
每个测试包含多个测试用例。第一行包含测试用例的数量 \(t\)(\(1 \le t \le 1000\))。测试用例的描述紧随其后。
每个测试用例的第一行包含 \(n\)(\(1 \le n \le 3 \cdot 10^5\))——数组 \(a\) 的长度。
每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)(\(1 \le a_i \le 10^{12}\))。
保证所有测试用例的 \(n\) 之和不超过 \(3 \cdot 10^5\)。
\(Output\)
对于每个测试用例,输出一个整数 —— 在执行一系列操作后,数组 \(a\) 的最大可能长度。
\(Sample\)
4
5
2 4 6 2 5
5
5 4 4 5 1
4
6 8 2 3
1
1


10
11
10
1
样例解析:
在第一个测试用例中,我们可以先选择 \(i = 4\),因为 \(a_4 = 5 + 1 - 4 = 2\)。在此之后,数组变为 \([2, 4, 6, 2, 5, 0, 0, 0]\)。然后我们可以选择 \(i = 3\),因为 \(a_3 = 8 + 1 - 3 = 6\)。在此之后,数组变为 \([2, 4, 6, 2, 5, 0, 0, 0, 0, 0]\),其长度为 10。可以证明,没有任何操作序列会使最终数组更长。
在第二个测试用例中,我们可以选择 \(i=2\),然后 \(i=3\),然后 \(ii=4\)。最终数组将是 \([5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]\),长度为 11。
思路:其实由这个式子\(a_i = |a| + 1 - i\)可得到\(a_i - i = |a| + 1\),当一个数可以进行操作时,其必然符合这个式子,不妨先求出\(a_i - i -|a| - 1\)作为特征值然后反过来用特征值去记录符合的下标,然后每次增加i-1时,可以去看看是否有符合的特征值存在,如果存在,则进行搜索,不在就返回。因为答案显然是没有一个固定策略可选,所以选择记忆化递归(dp的一种形式)然后从以0作为特征值去搜即可算出答案,对于每个阶段的增值可能最好用map记住,然后从其他地方搜过来时,时间复杂度就大大减小了

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll                                     long long
#define lowbit(x) (x & -x)
//#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
ll ksm(ll x, ll y)
{
ll ans = 1;
while (y)
{
if (y & 1)
{
ans = ans % mod * (x % mod) % mod;
}
x = x % mod * (x % mod) % mod;
y >>= 1;
}
return ans % mod % mod;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll n;
map<ll,set<ll>>q;
map<ll,ll>op;
ll dfs(ll cnt,ll z)//记忆化?
{
    if(op[cnt])
    {
        return op[cnt]+z;
    }
    ll ans=z;
  for(auto j:q[cnt])
  {
    ans=max(ans,dfs(cnt+j-1,z+j-1));
  }
   op[cnt]=ans-z;
   return ans;
}
ll a[450000];
int main()
{
    fio();
    ll t;
    cin>>t;
    while(t--)
    {
       op.clear();
       cin>>n;
       for(ll i=1;i<=n;i++)
       {
        cin>>a[i];
        if(a[i]>=(n-i+1)&&i!=1)
        {
            q[a[i]-(n-i+1)].insert(i);
        }
       }
       cout<<dfs(0,n)<<endl;
       q.clear();
    }
}

D1.The Endspeaker (Easy Version)

思路:先给个个人想法,用一维滚动数数组进行dp,dp[i]指dp到这位的最小费用,然后再每次数进行dp时进行双方更新,这种想法喜提WA3了,后面有时间再重新想想

标签:le,982,ll,Codeforces,数组,ans,Div,include,mod
From: https://www.cnblogs.com/cjcf/p/18533820

相关文章

  • Educational Codeforces Round 161 (Rated for Div. 2) - VP记录
    Preface先被A题硬控\(20\)分钟,有点不爽。又看到E题AC的人比D题多而去嗑E题去了,结果D题反而是我更能做的。将问题排序:根据你所需付出的努力,将能够最快解决的问题排在前面。(答题的次序为:以前做过的,容易的,不熟悉的,难的)——李博杰《骗分导论》\(\rmP_{114}\)所以......
  • CF963-Div2-E. Xor-Grid Problem
    CF963-Div2-E.Xor-GridProblem题意给定一个\(n\timesm\)的矩阵\(a\),有两种操作:选择一行,把每个数变成所在列所有数的异或之和。选择一列,把每个数变成所在行所有数的异或之和。求进行任意次操作后整个矩阵最小的美丽值。思路第一个发现:同一数异或两次相当于没有异......
  • LGR-204-Div.2 补题
    ContestlinkA比较明显的题,贪心往下做就可以。#include<bits/stdc++.h>usingi64=longlong;constexprintN=1e5+7;intk;inta[N];intmain(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin>>k; for(inti=1;i<=......
  • Codeforces Round 983 (Div. 2) 10.31 ABC题解
    CodeforcesRound983(Div.2)10.31题解A.Circuit数学(math)贪心(greedy)模拟(implementation)题意:有\(n\)盏灯,对应\(2\astn\)个开关,即每盏灯对应两个开关,开关打开或者关闭用\(1\)和\(0\)表示。给出\(2\astn\)个开关的状态,需要求解出可能开灯的最小数量和最大数量。......
  • DIV简单个人静态HTML网页设计作品 WEB静态个人介绍网页模板代码 DW个人网站制作成品
    ......
  • Educational Codeforces Round 171 (Rated for Div. 2) 题解
    A.PerpendicularSegments显然构造一个\(k\timesk\)的左下角是原点的正方形即可。voidslv(){ intx,y,k;Read(x,y,k); intmn=min(x,y); if(mn*mn*2>=k*k) Write(0,'',0,'',mn,'',mn,'\n'), Write(0,......
  • Codeforces Round 984 div3 个人题解(A~F)
    CodeforcesRound984div3个人题解(A~F)Dashboard-CodeforcesRound984(Div.3)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#include<cassert>#include<cmath>#in......
  • Codeforces Round 983 (Div. 2) 题解
    CodeforcesRound983(Div.2)题解CodeforcesRound983(Div.2)Problem-A-Codeforces解题思路考虑贪心,每个灯连两个开关,即两个开的灯可以关闭一盏灯,则灯数最多则尽可能让两个开关都开的灯尽量少,灯数最少则反之#include<bits/stdc++.h>#defineendl'\n'usingnam......
  • Codeforces Round 983 (Div. 2) A~D
    链接:CodeforcesRound983(Div.2)A:Circuit大意:    n个灯,每个灯连两个开关,每个开关只连一个灯,每个灯对应的两个开关如果异或为1就亮    现给定开关状态,求灯亮的最大和最小数量思路:    求最小数量的话,将开关为1的尽量组一起,我们发现,如果开关为1的......
  • Codeforces Round 983 Div2 A-C
    目录A-CircuitB-MediansC-TrinityD-总结与思考A-Circuit题目概述Alice刚刚制作了一个包含n个灯和2n个开关的电路。每个组件(灯或开关)有两种状态:开或关。灯和开关的排列方式如下:每个灯连接恰好两个开关。每个开关连接恰好一个灯。但并不知道每个开关......