题目链接:http://dluacm.cn/wp-content/uploads/2022/11/202211reshen.pdf
Problem RA 一些你应该知道的东西
把题面上代码复制粘贴过去即可AC。
注意空间只有4M,所以必须输入一组输出一组。
Problem RB 对对联
我校有名湖边上亭子的对联,按照提示去提问即可得到正确答案。
答案是“handeyingwuhoujiejusoucaiqingruosihuyouming”。
Problem RC 佩里科岛
我们只需要遍历一遍,根据题目“上岛后选择立即下岛”,所以收益最小为0,当我们遍历过程中遇到小于0的时候,直接置为0.
然后我们可以“选择在进入任意房间前上岛并在离开任意房间后下岛”,我们只需要取遍历过程中最大值即可。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
int main()
{
ll t;
scanf("%lld",&t);
while(t--)
{
ll n;
scanf("%lld",&n);
ll sum=0,ans=0;
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld",&x);
sum+=x;
if(sum<0) sum=0;
ans=max(sum,ans);
}
printf("%lld\n",ans);
}
return 0;
}
另外本题也可以使用线性dp解决。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N];
int dp[N];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
int ans=0;
for(int i=1;i<=n;++i){
dp[i]=max(dp[i-1]+a[i],a[i]);
ans=max(dp[i],ans);
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
Problem RD amiloac’s a+b
本题略有歧义,对a+b整体取余,不要求是结果是非负数。
在C/C++, JAVA言中,’%’运算符都是做取余运算,而在python中的’%’是做取模运算。
#include<stdio.h>
int main(){
long long a,b;
scanf("%lld%lld",&a,&b);
printf("%lld",(a+b)%10000000000007);
return 0;
}
Problem RE 删除数
注意空间只有4M,所以你存下所有的数再排序一定会爆空间。
相信大家都听过高斯小时候的故事,由于是连续整数,我们只需要求出它们的和,然后再求出区间和,减一下即可。
int main() {
long long a, b, n, sum = 0;
scanf("%lld%lld", &a, &b);
for (long long i = a; i < b; i++) {
scanf("%lld", &n);
sum += n;
}
printf("%lld", (b + a) * (b - a + 1) / 2 - sum );
return 0;
}
还有一种方法是用桶存相对位置
#include<bits/stdc++.h>
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define LL long long
#define all(x) x.begin(),x.end()
#define close() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=6e5;
bool vis[N];
void Solve(){
LL l,r,x;
cin>>l>>r;
int n=r-l+1;
for(int i=0;i<n-1;++i){
cin>>x;
vis[x-l]=true;
}
for(int i=0;i<n;++i){
if(!vis[i]){
cout<<l+i<<'\n';
return ;
}
}
}
int main(){
close();
Solve();
return 0;
}
Problem RF 鸽子的小心思
注意题面“这10个数在对10取模后互不同余,但是我想的数很大,你肯定猜不对。你就告诉我它们对10取余以后的结果就行。”
所以我们很容易想到其中一组答案“0 1 2 3 4 5 6 7 8 9”。
由于special judge出现未预料的问题,所以本题不计成绩,在此对所有参赛同学表示诚挚的歉意。