题解:AWC 0003
A
思路
没什么好说的，记得要开long long。
代码
ll n, k, a[N], b[N], cnt;
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];if(a[i]*b[i]>=k){cnt++;}}cout<<cnt;
}
B
思路
判断 \(L_i\) 与 \(R_{i-1}\) 是否相等即可。
代码
ll n;char a[N], b[N];int cnt;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}for(int i=1;i<=n;i++){if(a[i]==b[i-1]){cnt++;}}cout<<cnt;
}
C
思路
贪心+排序，注意排序时，是按 \(A_i - B_i\) 来排。
代码
ll n, cnt, k;
pll p[N];
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>p[i].fi>>p[i].se;}sort(p+1, p+1+n, [](pll x,pll y){return x.fi-x.se>y.fi-y.se;});for(int i=1;i<=n;i++){if(i<=k){cnt+=p[i].se;}else cnt+=p[i].fi;}cout<<cnt;
}
D
思路
一个滑动窗口，当 \(r-l+1 \lt k\) 或 \(sum \lt m\) 时，往后找，其中， \(sum=\displaystyle\sum_{i=l}^r A_i\) 。
代码
ll n, k, m, a[N], ans, sum;
int main(){cin>>n>>k>>m;for(int i=1;i<=n;i++){cin>>a[i];}int r=-1;for(int l=1;l<=n;l++){while(r+1<=n&&r-l+1<k){++r;sum+=a[r];}while(r+1<=n&&sum<m){r++;sum+=a[r];}if(sum>=m&&r-l+1>=k){ans+=n-r+1;}else break;sum-=a[l];}cout<<ans;
}
E
思路
这道题，我是拿状压dp写的，不知道的可以在oiwiki上看。
注意到 \(n,m \le 15\) ，所以写状压。设 \(dp_i\) 为可以拿二进制 \(i\) 中 \(1\) 的位置的物品，例如当 \(i=10\) 时， \(i=10=2^3+2^1\) ，它的二进制为 \((1010)_2\) ，表示我们可以拿第 \(1\) 个位置和第 \(3\) 个位置的物品。
那么，当 \(dp_i=1\) 时，它的状态转移式为:
\[dp_{当前没被选的物品的所有子集|i}=[子集内物品重量总和 \le c_i]
\]
初始状态 \(dp_0=1\) 。
当如果我们硬算子集内物品重量总和，我们的时间复杂度来到 \(O(mn\ 3^n)\) 太高了，我们要预处理所有子集物品重量总和。
代码
下标从0开始的
ll n, m, w[N], c[N];ll wg[1<<15];
bitset<1<<15>f;
int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>w[i];}for(int i=0;i<m;i++){cin>>c[i];}sort(c, c+m);int s=1<<n;s--;for(int i=1;i<=s;i++){int lb=i&-i;int j=__builtin_ctz(lb);wg[i]=wg[i^lb]+w[j];}f[0]=1;for(int i=0;i<m;i++){bitset<1<<15> g=f;for(int j=0;j<=s;j++){if(!f[j]){continue;}int res=j^s;for(int ss=res;ss;ss=(ss-1)&res){if(wg[ss]<=c[i]){g[j|ss]=1;}}}f=g;if(f[s]){break;}}cout<<(f[s]?"Yes\n":"No\n");
}
下标从1开始的
ll n, m, w[N], c[N];ll wg[1<<15];
bitset<1<<15>f;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>w[i];}for(int i=1;i<=m;i++){cin>>c[i];}sort(c+1, c+1+m);int s=1<<n;s--;for(int i=1;i<=s;i++){int lb=i&-i;int j=__builtin_ctz(lb);j++;wg[i]=wg[i^lb]+w[j];}f[0]=1;for(int i=1;i<=m;i++){bitset<1<<15> g=f;for(int j=0;j<=s;j++){if(!f[j]){continue;}int res=j^s;for(int ss=res;ss;ss=(ss-1)&res){if(wg[ss]<=c[i]){g[j|ss]=1;}}}f=g;if(f[s]){break;}}cout<<(f[s]?"Yes\n":"No\n");
}
本文来自 NoiPLE ，转载请注明原文链接：https://www.cnblogs.com/noiple-dequeee/p/19605891