直接输出
pi/ti,for遍历
#include <iostream>
using namespace std;
#define int long long
int a,b,c ;
double t=1.00;
signed main()
{cin>>a;int an=0;for(int i=1;i<=a;i++){cin>>b>>c;if(t>c*1.00/b){t=c*1.00/b;an=i;} }cout<<an<<endl;return 0;
}
用前缀和求重新启动的次数,特盘端点。
#include <iostream>
using namespace std;
#define int long long
const int n=1e6+11;
int a,b,c,l,r,d[n];
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>a;string t;cin>>t>>b;t=" "+t;for(int i=1;i<=a-1;i++){d[i]=d[i-1];if(t[i]=='1'&&t[i+1]=='0'){d[i]++;}}d[a]=d[a-1];d[a+1]=d[a];while(b--){cin>>l>>r;int v=d[r]-d[l-1];if(r==a+1){cout<<v<<endl;continue;}if(r<=a-1&&t[r]=='1'&&t[r+1]=='0'){v--;}cout<<v<<endl;}
}
背包
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int n=3e3+11;
int a,b[n],c[n],l,r,d[n],f[n];
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>a;for(int i=1;i<=a;i++){cin>>b[i];}for(int i=1;i<=a;i++){cin>>c[i];}for(int i=1;i<=a;i++){cin>>d[i];}for(int i=0;i<=3000;i++){f[i]=1e18;}f[b[1]]=0;int v=b[1];for(int i=1;i<=a;i++){for(int j=b[i]-1;j>=0;j--){f[j]=1e18;}for(int j=3000;j>=b[i]&&j>=d[i];j--){f[j]=min(f[j-d[i]]+c[i],f[j]);}}int p=1e18;for(int i=b[a];i<=3000;i++){p=min(p,f[i]);}if(p>=1e18){cout<<"-1"<<endl;}else{cout<<p<<endl;}
}
分别考虑每一位,组合数。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int n=1e6+11;
int a,b[n],c[n],l,r,d[n],f[n];
int ss(int x,int y)
{int p=1;while(y){if(y%2==1){p=p*x%mod;}x=x*x%mod;y/=2;}return p;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);a=9;int s=1;f[1]=1;for(int i=2;i<=100000;i++){s=s*10%mod;f[i]=(f[i-1]+s)%mod;}s=0;int ff=0;for(int i=1;i<=a;i++){cin>>b[i];if(b[i]!=0){ff++;}s+=b[i];}if(ff==1){cout<<f[s]%mod<<endl;return 0;}//cout<<"dfd"<<endl;d[s]=1;for(int i=s-1;i>=1;i--){d[i]=d[i+1]*i%mod;}c[0]=1;for(int i=1;i<=s-1;i++){c[i]=c[i-1]*i%mod;}//cout<<"ff"<<endl;int an=0;for(int i=1;i<=a;i++){if(b[i]==0)continue;if(b[i]==1){an=(an+(f[s]*i%mod))%mod;}elsean=(an+(((d[s-1-(b[i]-1)+1]*ss(c[b[i]-1],mod-2)%mod)*f[s])%mod*i)%mod)%mod;//cout<<an<<" "<<f[s]<<" "<<d[s-1-(b[i]-1)+1]<<endl;}cout<<an<<endl;
}
// 2 3 1 0 0 0 0 0 0