比赛链接:https://codeforc.es/contest/1715
总体难度除了AB题之外,其他的题几乎不可做。但是B题出现的问题太大了,WA了五次。最开始的思路没有直接去实现,因为感觉实现不了,最后发现自己写的n+k的复杂度根本过不去。回过头来又考虑的n+计算的思路。
A题:规律题,大意是给出一个n*m的矩阵,a位置(1,1),b位置(n,1),a需要走到右下角,b需要走到右上角。当a走到b走过的路时,可以直接一步走到任意b走过的位置,b同理。求总共最少需要多少步。
我们先让b走到右上角,考虑n和m的大小,令a走一个最小的数量转移到b。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) 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-48;ch=getchar();} return x*f; } void solve() { int n,m; cin>>n>>m; if(n==1&&m==1) cout<<0<<endl; else cout<<(m+n-2)+min(n,m)<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
B题:大意是给出n,k,b,s。n为长度为a的数组,对于每一个ai,我们使得ai/k 向下取整的 总和等于b,且ai的总和等于s。构造这么一组数据,多组可任意,没有输出-1。
很明显的我们可以从大到小考虑,但在这之前我认为应该先想好什么情况下不可能。首先,和的下限一定是k*b,上限一定是k*b+(n)*(k-1)。那么不合法条件就是下限大于s,上限小于s。ok,剩下的我们可以从大到小贪心地去考虑每一个数,我们尽量使得前一个数更大以给后面的数留出更少的分配量,直到数据构造完毕。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long 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-48;ch=getchar();} return x*f; } void solve() { ll n,k,b,s; scanf("%lld%lld%lld%lld",&n,&k,&b,&s); ll sum = s; if(k*b>s) cout<<-1<<endl; else if(k*b+n*(k-1)<s) cout<<-1<<endl; else { if(sum-k*b<k) printf("%lld ",sum),sum=0; else printf("%lld ",k*b+k-1),sum-=k*b+k-1; for(int i=2;i<=n;i++) { if(sum>=k-1) printf("%lld ",k-1),sum -=k-1; else printf("%lld ",sum),sum = 0; } cout<<endl; } } int main() { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
C题:大意是给出一个数组ai,根据连续情况,我们设置ans。
例如 3,2,2,2,5,4,4 ,对应s 为 1,2,2,2,3,4,4 ,我们要求的答案是对于从1-n开头的s相加。即 1+2+2+2+3+4+4为第一轮,1+1+1+2+3+3 为第二轮,以此轮推。每次操作给出i和x,替换ai为x。然后求出新的答案
我们可以预先求出ans为1开头情况下。然后+上n*(n-1) /2 就是最终答案。在这里有种感觉会是一个等差数列,因为我们把影响因子已经预先求出了。
之后每次查询,我们将两边的影响因子去掉,替换新的数后再增加影响因子。最后计算。
蛮不错的一个技巧题,技巧性很高,idea很难让人想到。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long 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-48;ch=getchar();} return x*f; } void solve() { ll n,m; n=read(),m=read(); vector<int> a(n+2,0); for(int i=1;i<=n;i++) a[i] = read(); ll ans = 0; for(int i=1;i<=n;i++) ans+=(a[i]!=a[i+1]) * (n-i)*i;//后面的都会+1 while(m--) { ll i ,x; i=read(),x=read(); ans-=(a[i]!=a[i-1])*(n-i+1)*(i-1);//减去后面的影响 ans-=(a[i]!=a[i+1])*(n-i)*i;//减去左边的影响 a[i] = x; ans+=(a[i]!=a[i-1])*(n-i+1)*(i-1);//加上后面的影响 ans+=(a[i]!=a[i+1])*(n-i)*i;//加上左边的影响 cout<<ans+n*(n+1)/2<<endl; } } int main() { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; solve(); }