【LGR-067】洛谷 1 月月赛 II & CSGRound 3 Div.2题解
T1 压岁钱
题目背景
祝大家庚子鼠年快乐！Best wishes!
也愿肺炎早日得到控制吧，中国加油！
新年到了，小 Z 总是能收到很多的压岁钱。
小 Z 是个非常喜欢氪金的玩家，所以时不时都会把压岁钱花掉一部分用来买皮肤和石头。
但是小 Z 又十分担心压岁钱没过几天就都被自己花完了。为此，小 Z 有封印大法，能够暂时的把自己的一部分钱封印起来（即无法花费），直到某一天解除封印后才能使用。
题目描述
一共存在有 mm 个事件，且事件分为以下的 33 种类型。
小 Z 得到了 aa 元压岁钱。
小 Z 花掉了 aa 元压岁钱用于买皮肤。
小 Z 把自己的 aa 元钱封印了起来，只有当第 bb 个事件发生前 11 秒才会解除封印，并保证每次小 Z 现有的钱大于等于封印的钱。
当小 Z 的钱在某个事件不够花时，小 Z 会感到不开心，同时钱不够花时小 Z 便不会花钱。
请告诉小 Z ，他的钱在几个事件中会不够花。
输入格式
第一行一个整数 m，用于表示事件发生的总数。
接下来的 m 行，首先一个整数 t，表示事件的类型。
如果 t=1 或 t=2，则接下来一个整数 a。
如果 t=3，则接下来两个整数 a,b。
输出格式
一行一个整数，表示钱不够花的事件数。
输入输出样例
输入 #1
3
1 10
2 20
2 10
输出 #1
1
输入 #2
5
1 10
3 5 5
2 10
1 10
2 20
输出 #2
1
说明/提示
【样例 1 解释】
第一天：收入 1010 元，余额 1010 元。
第二天：不够支出 2020 元，余额 1010 元。
第三天：支出 1010 元，余额 00 元。
总计：11 天。
【样例 2 解释】
第一天：收入 1010 元，余额 1010 元。
第二天：封印 55 元，余额 55 元。
第三天：不够支出 1010 元，余额 55 元。
第四天：收入 1010 元，余额 1515 元。
第五天：封印解开，支出 2020 元，余额 00 元。
总计：11 天。
分析:前70分就是白给，随便写，对于第三个事件，我们考虑在暴力的基础上用树状数组优化。树状数组维护第i个事件到第j个事件中，一共封印了多少钱，于是这道题就变成了一个区间修改，单点查询的裸题。我们先正常计算一共有多少钱，查询（2事件）的时候加上被封印的钱数进行判断即可(我存的封印钱数是负数)
上代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int m,t,a,b,ans;
int mon;
int fi[1000005];
int f[1000005];
inline int lowbit(int x)
{
return x&(-x);
}
inline int get(int x){
int sum=0;
for(int i=x;i>0;i-=lowbit(i)){
sum+=f[i];
}
return sum;
}
void add1(int x,int d){
for(int i=x;i<=m;i=i+lowbit(i)){f[i]=f[i]+d;}
return;
}
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
main(){
m=read();
ans=0;
int feng=0;
for(int i=1;i<=m;i++){
t=read();
if(t==1){
a=read();
mon+=a;//正经的钱数
}
else if(t==2){
a=read();
if(a>mon+get(i)){
ans++;
}
else{
mon-=a;
}
}
else if(t==3){
a=read();
b=read();
add1(i,-a);
add1(b,a);
}
}
cout<<ans;
return 0;
}
T2 斗牛
题目背景
又是一年过去了。小 Z 在春节期间可以好好的放松放松，于是小 Z 和小伙伴们玩起了牛哄哄（斗牛）。
游戏规则是这样的：
给定 5 张牌，分别从1∼10。你需要挑选其中的三张牌加起来是 1010 的倍数，另外两张牌的和的个位数则为你最后获得的点数，特别的，如果这两张牌的和是 10的倍数，则点数为 10，也叫做牛哄哄。如果不能构成 10 的倍数，则点数为 0，也叫做牛不拢。
如 5 3 2 3 4 的点数是 7，又叫做牛七。
小 Z 觉得玩的不过瘾，于是对上述规则进行了一些改变。
题目描述
给定 n张牌，牌的大小为1∼10。你需要挑选其中的 n-2 张牌加起来是 10 的倍数，另外两张牌和的个位数即为你所获得的点数。特别地，如果这两张牌的和是 10 的倍数，则点数为 10，也叫做牛哄哄。如果任意 n-2 张牌不能构成 10 的倍数，则点数为 0，也叫做牛不拢。
由于小 Z 想要更开心的玩耍，所以需要你来完成这个程序来帮助小 Z 在 11 秒内知道点数。
输入格式
第一行一个整数 n，表示一共有 n 张牌。
第二行 n 个整数，表示这 n 张牌的大小。
输出格式
一行一个整数，表示这局牌的点数，点数的范围是 0 \sim 100∼10。
输入输出样例
输入 #1
5
10 10 10 2 3
输出 #1
5
输入 #2
5
3 4 5 6 7
输出 #2
0
说明/提示
【样例 1 解释】
10 10 10三张牌凑成 10的倍数，2+3=5。
【样例 2 解释】
任意三张牌都不能凑成 10 的倍数。
(捆绑数据可挺艹)
题解：前50分n^2暴力乱跑就能过（这套题数据真的水），后面我们进行这样的考虑，把所有的牌加起来，和的各位数字所代表的数，以及这个数加十，如果能被表示为两张牌的和，那么就可以了（为什么只加十，因为两张牌最大是20）注意细节，这题白给。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,k,ans1,ans2;
int sum;
int you;
int pa[1000060];
int tt[10];
int pp[15];//是否出现过
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void pd1(){
int mid;
for(int i=1;i<=9;i++){
if(pp[i]){
mid=ans1-i;
if(mid==i){
if(pp[i]>=2){
if(i*2!=10&&i*2!=20)
cout<<(i*2)%10;
else cout<<10;
exit(0);
}
}
else if(pp[mid]){
if(i+mid!=10&&i+mid!=20)
cout<<(i+mid)%10;
else cout<<10;
exit(0);
}
}
}
return ;
}
inline void pd2(){
int mid;
for(int i=1;i<=9;i++){
if(pp[i]){
mid=ans2-i;
if(mid==i){
if(pp[i]>=2){
if(i*2!=10&&i*2!=20)
cout<<(i*2)%10;
else cout<<10;
exit(0);
}
}
else if(pp[mid]){
if(i+mid!=10&&i+mid!=20)
cout<<(i+mid)%10;
else cout<<10;
exit(0);
}
}
}
return ;
}
int main(){
n=read();
you=0;
if(n==5){
int zhn=0;
for(int i=1;i<=n;i++){
tt[i]=read();
zhn+=tt[i];
}
int lgr=zhn%10;
if(!lgr){
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if((tt[i]+tt[j])%10==0){
cout<<10;
exit(0);
}
}
}
cout<<0;
exit(0);
}
else {
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if((tt[i]+tt[j])%10==lgr){
cout<<lgr;
exit(0);
}
}
}
cout<<0;
exit(0);
}
}
else {
for(int i=1;i<=n;i++){
k=read();
if(k!=10){
you++;
pa[you]=k;
pp[k]++;
sum+=k;
}
}
if(you==1){
cout<<pa[you];
exit(0);
}
if(!you){
cout<<10;
exit(0);
}
ans1=sum%10;
ans2=ans1+10;
pd1();
pd2();
cout<<0;
}
return 0;
}
T3 游戏
题目背景
小 Y 和小 Z 是一对好朋友，他们在玩一个游戏。游戏只有一个回合。
题目描述
有一个牌堆，一共有 n 张牌，第 i 张牌上有一个数 a_i ，其中第一张牌是堆顶。
小 Z 先取牌，他可以从堆顶开始取连续若干张牌（可以取 0 张），取完的牌拿在手上，也就是不在牌堆里了。
然后小 Y 取牌，同样，她也可以从堆顶开始取连续若干张牌（可以取 0 张）。
如果一个人手上的牌的数字和大于 X，那么他的分数就是 0，否则分数就是数字和。
分数高的人获胜，如果一样高，则无人获胜。
小 Z 为了获胜，使用了透视挂，即他知道牌堆里每张牌上写的数。
现在问你对于满足 1≤X≤K 的所有整数 X，哪些可以使得小 Z 有必胜策略，即小 Z 取完后，不管小 Y 怎么取都一定会输。
输入格式
第一行一个整数 n，表示牌堆里有几张牌。
第二行 n 个整数，表示每张牌上写的数。
第三行一个正整数 KK，含义见题目描述。
输出格式
第一行一个整数，表示满足要求的 XX 的个数。
第二行从小到大依次输出满足要求的 XX，用空格隔开。
输入输出样例
输入 #1 复制
5
1 4 3 2 2
5
输出 #1 复制
3
1 2 3
说明/提示
【样例解释】
X=1,2,3 时，小 Z 取一张牌，小 Y 不管怎么取都是零分。
X=4时，小 Z 如果取 1 张，那么小 Y 取 1 张小 Y 就赢了；否则小 Z 只能是零分。
X=5时，小 Z 如果取 1 张，那么小 Y 取 1 张小 Y 就赢了；小 Z 如果取了 2 张，小 Y 也取2 张，平局；否则小 Z 只能是零分。
题解：我这题就写了个37分的暴力，后面还没写，明天再说（留坑）
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int n,k;
int a[1000050];
int sum[1000005];//前缀和
int ans[1000005];
int tmp=0;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];
k=read();
int zhn;
for(int i=1;i<=n;i++){
if(sum[i]>k){
zhn=i;
break;
}
}
if(n==1){//3分算法
if(a[1]>k)cout<<0;
else{
cout<<k-a[1]+1<<endl;
for(int i=a[1];i<=k;i++){
cout<<i<<" ";
}
}
}
else if(k==1){
if(a[1]>1) cout<<0;
else if(a[2]==1) cout<<0;
else cout<<1<<endl<<1;
}
else{
for(int i=1;i<=k;i++){//ANS MEIJV
for(int j=1;j<=zhn;j++){
if(sum[j]>i){
int zz=sum[j-1];//小z最大牌
for(int kk=j;kk<=n;kk++){
if(sum[kk]-sum[j-1]>i){
int jj=sum[kk-1]-sum[j-1];
if(jj<zz){
tmp++;
ans[tmp]=i;
}
break;
}
}
break;
}
}
}
cout<<tmp<<endl;
for(int i=1;i<=tmp;i++){
cout<<ans[i]<<" ";
}
}
return 0;
}
T4 (看到期望我就跑了QAQ以后再说吧)
总结：算法忘了，脑子秀逗了，我想回机房了///
投递韶音科技等公司6个岗位 >