AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=25;
char s[N][N];
int n,m;
void solve() {
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s[i][j];
}
}
int cnt=0;
string temp="vika";
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(s[i][j]==temp[cnt]){
cnt++;
break;
}
}
}
if(cnt==4) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+10;
int b[N];
int n;
void solve() {
cin>>n;
vector<int>ans;
for(int i=1; i<=n; i++) cin>>b[i];
ans.push_back(b[1]);
for(int i=2; i<=n; i++) {
int x=b[i-1];
if(b[i-1]<=b[i]&&b[i]<=b[i+1]) ans.push_back(b[i]);
else {
x--;
while(x>b[i]) x--;
if(x>0) ans.push_back(x);
ans.push_back(b[i]);
}
}
cout<<ans.size()<<endl;
for(auto v:ans) cout<<v<<' ';
cout<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}一开始都是一列一列竖着放置的,后将其横着放置(长的放在下面),问形状是否和之前一样
如果可行的话,变换后形状是不变的,那么一列一列看,变换后的第一列高度和之前一样,假设高度为a[1],那么至少得有a[1]列高度大于等于1才能拼成第一列,同理至少得有a[2]列高度大于等于2才能拼成第二列...
可以用树状数组来记录有几列高度是小于等于x的,即为sum(x),然后mp[x]记录有几列高度等于x,n-(sum(x)-mp[x])即为有几列高度大于等于x
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N];
int tr[N];
int n;
//树状数组
int lowbit(int x) {
return x & -x;
}
void add(int x,int c) {
for(int i=x; i<=n; i+=lowbit(i)) tr[i]+=c;
}
int sum(int x) {
int res=0;
for(int i=x; i; i-=lowbit(i)) res+=tr[i];
return res;
}
void solve() {
cin>>n;
map<int,int>mp;
memset(tr,0,sizeof tr);
for(int i=1; i<=n; i++) {
cin>>a[i];
mp[a[i]]++;//统计a[i]的个数
add(a[i],1);
}
bool flag=true;
for(int i=1; i<=n; i++) {
if(n-(sum(i)-mp[i])<a[i]) {
cout<<"No"<<endl;
return;
}
}
cout<<"Yes"<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}一开始以为是dp,选与不选,然后选m个,但是状态转移不太好写
实际上这题是贪心
首先,假如我们选第一个,第三个,第五个,那么总共的娱乐值为a1+a3+a5-1*d-2*d-2*d=a1+a3+a5-5*d,所以我们将选的娱乐值全部加起来,然后看下标最大的是哪一个,记为i,再减去d*i即可
于是,我们可以贪心,将选择的放在优先队列中(肯定得放大于0的),然后当队列中的个数小于m时,就继续放,当队列中的个数等于m时,由于最大的下标一定,即减去的d*i一定,所以我们要使得放入队列的娱乐值这和最大,那么就要将队头(娱乐值最小的)和即将放入的比较,删去娱乐值最小的
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N];
int n,m;
ll d;
void solve() {
cin>>n>>m>>d;
for(int i=1; i<=n; i++) cin>>a[i];
priority_queue<int,vector<int>,greater<int>>q;
ll sum=0;
ll ans=0;
for(int i=1; i<=n; i++) {
if(a[i]<0) continue;
if(q.size()==m&&q.top()<a[i]) {
sum-=q.top();
q.pop();
}
if(q.size()<m) {
q.push(a[i]);
sum+=a[i];
}
ans=max(ans,sum-d*i);
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}组合数
首先,对于不同种的球,假设有x种球,那么组合数就是C(x,2),但是注意题目的要求是exactly,也就是说刚好n种
先二分找到第一个满足C(l,2)大于等于n的l,先特判如果C(l,2)刚好等于n,那么直接输出l
否则我们只能取l-1个不同种类的球,组合数就是C(l-1,2),然后补足剩下的,假设还差diff个,那么就在原来已经有的球中选diff种,每种球加一个,那么答案即为l-1+diff
可以保证,diff一定小于等于l-1,因为C(l-1,2)小于n,C(l,2)大于等于n,diff等于n-C(l-1,2),所以diff小于等于C(l,2-C(l-1,2),即l-1
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
#define endl '\n'
#define int long long
using namespace std;
typedef long long ll;
int n;
void solve() {
cin>>n;
int l=0,r=2e9;
while(l<r){
int mid=(l+r)/2;
if(mid*(mid-1)/2>=n) r=mid;
else l=mid+1;
}
if(l*(l-1)/2==n){
cout<<l<<endl;
return;
}
int diff=n-(l-1)*(l-2)/2;
int res=l-1+diff;
cout<<res<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}原本是想用贪心的,优先杀死能量值大的怪兽,于是写下了以下代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define endl '\n'
#define int long long
using namespace std;
typedef long long ll;
int w,f;
int n;
void solve() {
cin>>w>>f;
cin>>n;
priority_queue<int>q;
for(int i=1; i<=n; i++) {
int x;
cin>>x;
q.push(x);
}
//标记一下哪个增长的快
int flag;
if(w>f) flag=1;//sum1增长的快
else flag=2;//sum2增长的快
int cnt=0;//记录次数
int sum1=0,sum2=0;
while(q.size()) {
sum1+=w,sum2+=f,cnt++;
if(flag==1) {
while(q.size()&&sum1>=q.top()) {
sum1-=q.top();
q.pop();
}
while(q.size()&&sum2>=q.top()) {
sum2-=q.top();
q.pop();
}
} else if(flag==2) {
while(q.size()&&sum2>=q.top()) {
sum2-=q.top();
q.pop();
}
while(q.size()&&sum1>=q.top()) {
sum1-=q.top();
q.pop();
}
}
}
cout<<cnt<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}但是从第一个样例可以看成,似乎贪心并不可行,优先杀死大的并不能得到正确答案
解析:
怪兽的生命值的总和是一定的,我们选择一部分用水杀死,一部分用火杀死
然后具体哪些用水杀死,我们枚举所有的组合,相当于背包问题,选择哪些成为一个组合
假设生命值和为x用水杀死,生命值和为y用火杀死
那么次数即为max(x/w+(x%w!=0),y/f+(y%f!=0)),然后每次取min即可
法一:
枚举所有的组合可以用bitset,可以组合出的血量标记为1
首先,b[0]初始化为1,然后对于一个怪兽的生命值a,b|=b
由此,假设第一个怪兽的生命值为2,第二个怪兽的生命值为5,第三个怪兽的生命值为6,那么第0,2,5,6以及2+5,2+6,5+6位都标记为1
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<bitset>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=1e6+10;
int a[N];
int w,f;
int n;
void solve() {
cin>>w>>f;
cin>>n;
bitset<N>bt;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
bt[0]=1;
for(int i=1;i<=n;i++) bt|=bt<<a[i];
int ans=2e9;
for(int i=0;i<=sum;i++){
if(!bt[i]) continue;
int x=i/w+(i%w!=0);
int y=(sum-i)/f+((sum-i)%f!=0);
ans=min(ans,max(x,y));
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}法二:
背包
dp[i][j]表示从前i个怪兽里选,总的生命值为j是否可行
for(int i=1;i<=n;i++){
for(int j=a[i];j<=sum;j++){
dp[i][j]|=dp[i-1][j-a[i]];
}
}
然后由于dp[100][1e6]会爆空间,所以优化成一维
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=1e6+10;
int a[N];
int dp[N];
int w,f;
int n;
void solve() {
cin>>w>>f;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=sum;j>=a[i];j--){
dp[j]|=dp[j-a[i]];
}
}
int ans=2e9;
for(int i=0;i<=sum;i++){
if(!dp[i]) continue;
int x=i/w+(i%w!=0);
int y=(sum-i)/f+((sum-i)%f!=0);
ans=min(ans,max(x,y));
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}