1783C - Yet Another Tournament
分析
正解思路是贪心
开始自己也想的贪心:首先显然打败的人数越多越好,然后选择权值最小的人打败。
这个思路前半部分没问题,后半部分过不了样例的第二个数据。
现在打败人已经确定。问题是要具体打败哪几个人。开始想用dp来解决,但不会写,于是看题解。
题解思路:首先确定打败的人数winn,然后看跟自己对决前,n个人的胜场数。如果我能在打败
的人数中,打败胜场数同样为winn的人,那答案为n-winn;否则答案为n-winn+1(具体可以自己推导一下)
反思
在问题的后半部分,正解只需根据规律,关注是否打败了胜场数同样为winn的人即可。因为没找规律导致贪心思路在后半段出现了问题。
另
本题还有一种二分写法,详见 知乎cup-pyy 的题解。
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int n,m,b[500005];
int vis[500005];
pair<int,int> a[500005];
void solve(){
memset(vis,0,sizeof(vis));
int xx=0,winn=0,sum=0;
cin>>n>>m;
rep(i,1,n){
cin>>a[i].first;
a[i].second=i-1;//胜场num
b[i]=a[i].first;
}
sort(a+1,a+n+1);
rep(i,1,n){
if(sum+a[i].first<=m){
sum+=a[i].first;
winn++;
vis[a[i].second]=1;
}
else break;
}
if(vis[winn] || sum-a[winn].first+b[winn+1]<=m){
cout<<max(1,n-winn)<<"\n";
}
else{
cout<<n-winn+1<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
1783D - Different Arrays
分析
一道动态规划题
第i位置的元素会引起第i+1位置的元素的+-变化。考虑以数组元素能变成的数字为状态进行转移。
设现有元素,有或,则状态转移方程可表示为:
(写题时考虑了在本轮+-中,若存在某个与另一个相同,则岂不是把这个值向转移了两次,从而导致了重复? 但其实并没有重复。因为这两个虽然相同,但转移到当前数值的“路径不同”,因此这仍是两个不同的方案,这两次转移并不重复)
此外,对于上述dp方程,若,则+-结果相同,dp方程只需要用一次。
另外还要考虑数组元素可能减成负数,无法用数组下标来表示负数状态,所以要把所有状态加上一个值来保证所有状态都以非负数表示。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int maxn=1e5;
const int mod=998244353;
int n,a[305];
int f[2][maxn*2+10];
void solve(){
cin>>n;
rep(i,1,n){
cin>>a[i];
}
int true_zero=100000, ans=0;
f[0][a[2]+true_zero]=1;
rep(i,2,n-1){
rep(j,1,maxn*2){
f[(i+1)&1][j]=0;
}
rep(j,1,maxn*2){ //以第i+2个数+-第i+1个数后的数值为状态进行转移
if(f[i&1][j] == 0) continue;
if(j==(0+true_zero)){
f[(i+1)&1][a[i+1]+j] += f[i&1][j];
f[(i+1)&1][a[i+1]+j] %= mod;
}
else{ //注意这种表示法:
//a[i+1]+(j-true_zero)+true_zero,先加上原来的数,再加上偏置
//a[i+1]-(j-true_zero)+true_zero,先减去原来的数,再加上偏置
f[(i+1)&1][a[i+1]+j] += f[i&1][j];
f[(i+1)&1][a[i+1]+j] %= mod;
f[(i+1)&1][a[i+1]-j+2*true_zero] += f[i&1][j];
f[(i+1)&1][a[i+1]-j+2*true_zero] %= mod;
}
}
}
rep(i,1,maxn*2+5){
ans+=f[n&1][i];
ans%=mod;
}
cout<<ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}