首页 > 其他分享 >The 2022 ICPC Asia Regionals Online Contest (I) C L A

The 2022 ICPC Asia Regionals Online Contest (I) C L A

时间:2023-08-16 20:55:45浏览次数:47  
标签:pre suf cnt Contest int res Asia ICPC ++

The 2022 ICPC Asia Regionals Online Contest (I)

C

统计度的大小,算贡献,特判 \(n = 1\)

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

typedef long long ll;

int n, d[N];
vector<int> e[N];
ll res = 0;
void dfs(int u, int from)
{
	int cnt = 0;
	for(auto v : e[u])
	{
		if(v == from)	continue;
		cnt++;
		dfs(v, u);
	}
	if(u != 1)
		res = res + max(cnt - 1, 0);
}

void solve()
{
	res = 0;
	cin>>n;
	if(n == 1)
	{
		cout<<1<<'\n';
		return;
	}
	for(int i = 1; i <= n; i++)
	{
		d[i] = 0;
		e[i].clear();
	}
	for(int i = 1; i <= n - 1; i++)
	{
		int u, v;	cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
		d[u]++, d[v]++;
	}
	dfs(1, 0);
	res += 2;
	if(d[1] >= 2)
		res += (d[1] - 2);
	cout<<res<<'\n';
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tc;	cin>>tc;
	while(tc--)
		solve();

}

L

动态规划

预处理所有不合法情况

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

typedef long long ll;

int n, m, res;
int a[N], b[N], f[N][27], g[N][27];
string s, t;    
bool st[N][27], vis[27];
void solve()
{
    cin>>s>>t;
    n = s.size(), m = t.size();
    s = "?" + s, t = "?" + t;
    for(int i = 1; i <= n; i++)
        a[i] = s[i] - 'a' + 1;
    for(int i = m; i >= 1; i--)
    {
        b[i] = t[i] - 'a' + 1;
        for(int j = 1; j <= 26; j++)
            if(vis[j]) st[b[i]][j] = true;
        vis[b[i]] = true;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= 26; j++)
            f[i][j] = f[i - 1][j] + (vis[a[i]] == false), res = max(f[i][j], res);
        if(vis[a[i]] == false)  continue;   
        f[i][a[i]] = max(1, f[i][a[i]]);
        res = max(f[i][a[i]], res);
        for(int j = 1; j <= 26; j++)
            if(st[j][a[i]] == false)
                f[i][a[i]] = max(f[i - 1][j] + 1, f[i][a[i]]),
                res = max(f[i][a[i]], res);
    }
    cout<<res<<'\n';
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();

}

A

观察得:

  1. 一团大小为\(k\) 的 \(1\) 可以删掉 \(\dfrac{k}{2} + k \% 2\)

  2. 对于 \(1,1,0,\dots,0,1,1\), 首尾的 \(1\) 会相互影响,但对于记录一下其前后缀就可以得出首尾的 一团 \(1\) 的大小

  3. 那么预处理出删的次数即可

    const int N = 1e6 + 10;
    
    int n, q, pre[N], suf[N], f[N], cnt;
    string s;
    void solve()
    {       
        cin>>n>>q;
        cin>>s; s = "?" + s;
        for(int i = 1; i <= n; i++)
        {
            if(s[i] == '1') cnt++;
            else cnt = 0;
            pre[i] = cnt;
            f[i] = f[i - cnt - 1] + (cnt / 2 + cnt % 2);
        }
        cnt = 0;
        for(int i = n; i >= 1; i--)
        {
            if(s[i] == '1') cnt++;
            else cnt = 0;
            suf[i] = cnt;
        }
        for(int i = 1; i <= q; i++)
        {
            int l, r;   cin>>l>>r;
            int tl = l + suf[l], tr = r - pre[r];
            if(suf[l] == 0 && pre[r] != 0)
                tl++;
            if(pre[r] == 0 && suf[l] != 0)
                tr--;
            int t = suf[l] + pre[r];
            t = t / 2 + t % 2;
            int add = 0;
            if(tl <= tr)
                add = f[tr] - f[tl - 1];
            int res = (r - l + 1) / 3 - t - add;
            res = max(0, res);
            cout<<res<<'\n';
        }
        return;
    }
    

标签:pre,suf,cnt,Contest,int,res,Asia,ICPC,++
From: https://www.cnblogs.com/magicat/p/17636155.html

相关文章

  • 文件解压 //problem/2928 or /contest/1709/problem/3
    字符串套递归#include<bits/stdc++.h>usingnamespacestd;chars[1005];intn,i;stringwork(){stringp;intt=0;while(++i<=n){if(s[i]>='0'&&s[i]<='9'){t=s[i]-'0......
  • 2021 ICPC 上海 DEHI
    2021ICPC上海DEHI链接:The2021ICPCAsiaShanghaiRegionalProgrammingContestD.StrangeFractions题意:给你\(p,q\),让你找正整数\(a,b\),使得\(\dfrac{p}{q}=\dfrac{a}{b}+\dfrac{b}{a}\)。如果不存在,输出\(0\)\(0\)。思路:简单数学。推柿子+\(\gcd\)因为有\(\dfrac{......
  • 议题预告 | Pulsar Summit Asia 2022:Day 2 - 英文演讲
    关于PulsarSummitPulsarSummit是ApachePulsar社区年度盛会,它将分布在世界各地的ApachePulsar项目Contributor、Committer和各企业CTO/CIO、开发者、架构师、数据科学家,以及消息和流计算社区的精英召集在一起。于此盛会,大家分享实践经验、交流想法、探讨关于Pulsar项......
  • AtCoder Beginner Contest 314
    AtCoderBeginnerContest314-AtCoderA-3.14(atcoder.jp)题目提供了100位,所以直接用字符串输出#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);strings="3.14......
  • AtCoder Beginner Contest 314
    AtCoderBeginnerContest314-AtCoderA3.14voidsolve(){strings="3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";intn;cin>>n;cout<<s.substr(0,n......
  • Contest1319 - 期末习题汇总(二) 计算机基础---进制转换相关
    题目描述将十进制的1234输出将八进制的1234对应其十进制数进行输出将十六进制的1234对应其十进制数进行输出输入无输出1234D=1234D1234O=668D1234H=4660D样例输出1234D=1234D1234O=668D1234H=4660D 代码:#include<iostream>#include<iomanip>usingnamespacestd;in......
  • AtCoder Beginner Contest 314 A - Ex题解
    AtCoderBeginnerContest314A-3.14嗯,你可以用string存小数点后的...B-Roulette对于每一个金额,用个vector存pair<>存一个人赌了多少,以及是哪一个人。C-RotateColoredSubsequence每种数用个双向链表记下来。D-LOWER我们观察到,对于2,3操作,只有最后一次有用,且......
  • AtCoder Beginner Contest 214
    AtCoderBeginnerContest214-AtCoder [ABC214D]SumofMaximumWeights ------------------------------(典)题意:给出一颗N-1 条边的树,求树上任意两点间路径上的最大值的和这种问题考虑每条边单独看贡献,但是刚开始没太想明白怎么计算贡献,后面看了洛谷题解才懂了-......
  • UESTC 2023 Summer Training #23 for div2/2022-2023 ACM-ICPC Latin American Region
    Preface今天这场签到巨多,和昨天那场形成了鲜明的对比但可惜后盘的时候我划了太久的水,最后接了B题然后没调出来成为战俘最气的是赛后发现原来是没注意输出格式,本来可以说一遍过的题结果没写过,属实可惜,就当长教训了以后一定要尤其注意输入输出格式A.AskingforMoneyORZ徐......
  • 详解Jvm中时区设置方式,推荐 代码中TimeZone.getTimeZone("Asia/Shanghai") 而不使用Ti
    详解Jvm中时区设置方式原文链接:https://www.45fan.com/article.php?aid=20090934958860528675768691这篇文章memo一下Jvm中关于时区设定的基础操作。Java的时区设定这里列出如下三种方式方式说明TimeZone.setDefault方式通过java的utils下的TimeZone进行动态设定......