当前位置： 首页 > news >正文

【AtCoder】ARC071

news 来源：原创 2024/5/10 20:36:47

ARC071

C - 怪文書 / Dubious Document

题目大意：给n个字符串，每个字符串可以通过扔掉一些字母将剩下的字母重排得到新的字符串，求n个字符串都能拼出的字符串且长度最大，若有多个输出字典序最小

直接对每个字母取个min即可

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 10005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 +c - '0';
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    out(x / 10);
    }
    putchar('0' + x % 10);
}
int N;
char s[55];
int t[30],a[30];
void Solve() {
    read(N);
    for(int i = 0 ; i < 26 ; ++i) a[i] = 50;
    for(int i = 1 ; i <= N ; ++i) {
    scanf("%s",s + 1);
    int l = strlen(s + 1);
    memset(t,0,sizeof(t));
    for(int j = 1 ; j <= l ; ++j) t[s[j] - 'a']++;
    for(int j = 0 ; j < 26 ; ++j) a[j] = min(a[j],t[j]);
    }
    for(int i = 0 ; i < 26 ; ++i) {
    for(int j = 1 ; j <= a[i] ; ++j) {
        putchar('a' + i);
    }
    }
    enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

D - 井井井 / ###

大意：给n条和x轴平行的线，m条和y轴平行的线，求所有矩形的面积和

就是二维的任意连续子段和相乘即可

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 10005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 +c - '0';
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N,M,s[2],l[2];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void update(int &x,int y) {
    x = inc(x,y);
}
void Solve() {
    read(N);read(M);
    int x;
    for(int i = 1 ; i <= N ; ++i) {
    read(x);
    x = (x + MOD) % MOD;
    update(l[0],inc(mul(i - 1,x),MOD - s[0]));
    update(s[0],x);
    }
    int y;
    for(int i = 1 ; i <= M ; ++i) {
    read(y);
    y = (y + MOD) % MOD;
    update(l[1],inc(mul(i - 1,y),MOD - s[1]));
    update(s[1],y);
    }
    out(mul(l[0],l[1]));
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

E - TrBBnsformBBtion

大意：一个只包含AB的串，A可以变成BB，B可以变成AA，三个连续相同字母可以删除，问S的一个子串能否变成T的一个子串

把A标值成1，把B标值成2，可以发现一个字符串在取模3意义下和不改变

然后可以发现21可以变成12

用数学归纳法可以证明两个字符串和相等一定可以互相转化，就是把S通过操作和T调成等长度，如果第K + 1个数相等，那么S可以转化成T

其余情况不妨是S的K + 1是1，T的K + 1是2，如果S中含有2可以用21和12的交换把2换过去，否则S就全是1，T就全是2，此时两者长度必然是3的倍数，那么把S所有的1变成2，删掉3的整数倍个2可得到T

这道题的题目名称有点皮

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 +c - '0';
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    out(x / 10);
    }
    putchar('0' + x % 10);
}
char s[2][MAXN];
int Q;
int sum[2][MAXN];
void Solve() {
    scanf("%s%s",s[0] + 1,s[1] + 1);
    int l = strlen(s[0] + 1);
    for(int i = 1 ; i <= l ; ++i) {
    sum[0][i] = sum[0][i - 1];
    if(s[0][i] == 'A') sum[0][i] += 1;
    else sum[0][i] += 2;
    }
    l = strlen(s[1] + 1);
    for(int i = 1 ; i <= l ; ++i) {
    sum[1][i] = sum[1][i - 1];
    if(s[1][i] == 'A') sum[1][i] += 1;
    else sum[1][i] += 2;
    }
    read(Q);
    int a,b,c,d;
    for(int i = 1 ; i <= Q ; ++i) {
    read(a);read(b);read(c);read(d);
    if((sum[0][b] - sum[0][a - 1]) % 3 == (sum[1][d] - sum[1][c - 1]) % 3) {puts("YES");}
    else puts("NO");
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

F - Infinite Sequence

就是如果一个大于等于2的数，连了一个大于等于2的数，那么之后的所有都会被固定

那么我们就算前i个没有出现这种情况的方案数

我们可以在i个后面接上固定下来的情况，也可以第i个直接到终点，也可以是某种X111111....的1需要延续到N之后

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 1000005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 +c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void update(int &x,int y) {
    x = inc(x,y);
}
int N;
int sum[MAXN],dp[MAXN];
void Solve() {
    read(N);
    dp[0] = 1;
    sum[0] = 1;
    int ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
        update(dp[i],dp[i - 1]);
        if(i >= 3) update(dp[i],sum[i - 3]);
        sum[i] = inc(sum[i - 1],dp[i]);
    }
    for(int i = 0 ; i <= N ; ++i) {
        if(i == N - 1) {
            update(ans,mul(dp[i],N - 1));
        }
        else if(i == N) {
            update(ans,dp[i]);
        }
        else {
            update(ans,mul(dp[i],mul(N - 1,N - 1)));
        }
        if(i < N - 1) {
            int t = N - i - 1;
            update(ans,mul(dp[i],N - t));
        }
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

板刷了三页AtCoder……
加油。。。。还有一页半……？

转载于:https://www.cnblogs.com/ivorysi/p/10770310.html

相关文章：

  • [Markdown] 02 简单应用 第二弹
  • webmagic爬虫框架抽取元素
  • ScriptManager的几个属性和方法
  • Alpha冲刺(3/10)——2019.4.25
  • 接口测试基础
  • MySql综合知识汇总
  • FullCalendar Timeline View 使用
  • 08-图9 关键活动 (30 分)
  • Numpy用户指南
  • 涨姿势：抛弃字母、数字和下划线写SHELL
  • c++实现扫描检测硬件改动
  • 百度地图API获取数据
  • leetcode 338. 比特位计数(Counting Bits)
  • 2019-04-30vmware虚拟机安装macos 10.8格式为iso
  • 【Python爬虫】听说你又闹书荒了？豆瓣读书9.0分书籍陪你过五一
  • “寒冬”下的金三银四跳槽季来了，帮你客观分析一下局面
  • 【附node操作实例】redis简明入门系列—字符串类型
  • - C#编程大幅提高OUTLOOK的邮件搜索能力!
  • dva中组件的懒加载
  • IP路由与转发
  • JS专题之继承
  • leetcode46 Permutation 排列组合
  • LeetCode541. Reverse String II -- 按步长反转字符串
  • MD5加密原理解析及OC版原理实现
  • MQ框架的比较
  • php ci框架整合银盛支付
  • vue：响应原理
  • 表单中readonly的input等标签，禁止光标进入（focus）的几种方式
  • 少走弯路，给Java 1~5 年程序员的建议
  • 微信小程序实战练习（仿五洲到家微信版）
  • 译米田引理
  • 用jquery写贪吃蛇
  • ​sqlite3 --- SQLite 数据库 DB-API 2.0 接口模块​
  • ​用户画像从0到100的构建思路
  • #AngularJS#$sce.trustAsResourceUrl
  • #vue3 实现前端下载excel文件模板功能
  • #我与Java虚拟机的故事#连载10： 如何在阿里、腾讯、百度、及字节跳动等公司面试中脱颖而出...
  • $$$$GB2312-80区位编码表$$$$
  • ()、[]、{}、(())、[[]]命令替换
  • (poj1.2.1)1970(筛选法模拟)
  • （附源码）python旅游推荐系统 毕业设计 250623
  • （附源码）spring boot公选课在线选课系统 毕业设计 142011
  • (三)模仿学习-Action数据的模仿
  • （实战篇）如何缓存数据
  • （转）Scala的“=”符号简介
  • （转）利用PHP的debug_backtrace函数，实现PHP文件权限管理、动态加载 【反射】...
  • （最优化理论与方法）第二章最优化所需基础知识-第三节：重要凸集举例
  • **CI中自动类加载的用法总结
  • ... 是什么 ？... 有什么用处?
  • .NET Core WebAPI中使用Log4net 日志级别分类并记录到数据库
  • .NET Core 控制台程序读 appsettings.json 、注依赖、配日志、设 IOptions
  • /3GB和/USERVA开关
  • @ 代码随想录算法训练营第8周（C语言）|Day57（动态规划）
  • @ModelAttribute注解使用
  • @Resource和@Autowired的区别