//毋庸置疑最好的题目是h题,其次就是g题;(j离我有点远)
//第一种暴力n方前缀和去模拟判断。甚至杰哥用bfs也过
//第一种dp,(me)
//我的想法是利用dp的每个状态是可以转化,但是又是“独立”的
//所以设置dpij,i表示在第几个了,j表示花费的时间
//由于是判断题,所以用bool来传递
//每次更新某个值,可以往前和往后
//完全无脑的dp;
//状态表示:在t时间点在i点是否合法
//状态转移:根据题意,可以往前也可以往后
//并且采用刷表法,外层for表示时间,内层循环点(非背包模型)//注意这样子
//才能正确更新,因为是纯模拟走路(其实就是dfs),时间是一直往前,点是不///断变化
//if(dp[i][t])
//dp[i+1][t + vc[i+1]] = true,
//dp[i-1][t + vc[i]] = true;
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, tt;
cin >> n >> tt;
vector<int> vc(n+1, 0);
for(int i=1; i<=n; i++) cin >> vc[i];
//for
//cin>>pre
vector<vector<bool>> dp(n+1, vector<bool>(tt+1, false));
dp[0][0] = true;
for(int t=0; t<=tt; t++){
for(int i=0; i<=n; i++){
if(dp[i][t]){
if(i < n && t + vc[i+1] <= tt){
dp[i+1][t + vc[i+1]] = true;
}
if(i > 0 && t + vc[i] <= tt){
dp[i-1][t + vc[i]] = true;
}
}
}
}
if(dp[n][tt]) cout << "YES\n";
else cout << "NO\n";
}
//标答案的dp,我觉得更好更妙,直接利用背包dp和题目的性质:假设A——B——C
//反着走,从a到c,c到a,其实状态直接等于,单独的a到b,b到a,b到c,c到b
//反正就是类似于绳子绕圈
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1005];
bool dp[50005];
int main()
{
dp[0]=1;
ll n,k;
ll sum=0;
cin>>n>>k;
for (int i=0;i<n;i++) {
cin>>a[i];
sum+=a[i];
}
// 每次站都至少到一次,因此如果k小于sum那么不可能
if (sum>k) {
cout<<"NO"<<endl;
return 0;
}
// k减去sum后,剩余的时间可以通过每一段距离来回来抵消。
k-=sum;
// dp[j] 代表是否可以刚好花费 j 单位时间
for (int i=0;i<n;i++) {
for (int j=a[i]*2;j<=k;j++) {
if (dp[j-a[i]*2]) {
dp[j]=1;
}
}
}
if (dp[k]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
这道题fang哥的on解法很妙,小帅哥的贡献nlongn也很秒。我的nlognlogn就不妙了
小帅哥的贡献解法
#include <bits/stdc++.h>
using namespace std;
#define int long long
int l[1000010],r[1000010];
int vc[1000010];
int pre[1000010],sur[1000010];
priority_queue<int, vector<int>, greater<int>> lq, rq;
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>vc[i];
}
pre[1]=vc[1];
for(int i=2;i<=n;i++) pre[i]=min(vc[i],pre[i-1]);
sur[n]=vc[n];
for(int i=n-1;i>=1;i--) sur[i]=min(vc[i],sur[i+1]);
int x=0;
for(int i=n;i>=1;i--){
if(vc[i]>pre[i]){
x++;
lq.push(vc[i]);
}
while(!lq.empty()&&pre[i]>=lq.top()){
x--;
lq.pop();
}
l[i]=x-(vc[i]>pre[i]);//不包括当前正在处理的
}
x=0;
for(int i=1;i<=n;i++){
if(vc[i]>sur[i]){
x++;
rq.push(vc[i]);
}
while(!rq.empty()&&sur[i]>=rq.top()){
x--;
rq.pop();
}
r[i]=x-(vc[i]>sur[i]);
}
int ans=0;
for(int i=1;i<n;i++){
ans=max(ans,l[i]+r[i+1]);
}
cout<<ans<<"\n";
}
//fang哥的主要难在思路上
void solve(){
int n = 0;
cin>>n;
vector<int>arr(n+1);
int mn1 = 1e9+8,mn2 = 1e9+8,num1 = 0,num2 = 0;
//统计最小和次小。
for(int i = 1;i<=n;i++){
cin>>arr[i];
if(arr[i]<=mn1){
if(arr[i]<mn1){
mn2 = mn1;
num2 = num1;
mn1 = arr[i];
num1 = 1;
}else {
num1++;
}
}else if(arr[i]<=mn2){
if(arr[i]<mn2){
mn2 = arr[i];
num2 = 1;
}else{
num2++;
}
}
}
//分类
if(num1==1&&num2==1){
cout<<n-1<<"\n";
}else if(num1>=2){
cout<<n-num1<<"\n";
}else if(num1==1&&num2>1){
int dex = 0;
for(int i = 1;i<=n;i++){
if(arr[i]==mn1){
dex = i;
break;
}
}
int numl = 0,numr = 0;
for(int i = 1;i<=dex;i++){
if(arr[i]==mn2){
numl++;
}
}
for(int i = dex;i<=n;i++){
if(arr[i]==mn2){
numr++;
}
}
cout<<n-1-min(numl,numr)<<"\n";
}
}
dvi2(猜猜乐)
有趣的一道题,博弈题,直线内两个人都走,不走择输:
考虑过程中两个人都走的情况:无论怎么走都不会改变两者的距离奇偶性;
分析到,如果奇数,那么a必定胜利(a先走);如果是偶数,对称的b赢(类比于b先走)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n,a,b;
cin>>n>>a>>b;
if(abs(a-b)&1){
cout<<"NO\n";
}else{
cout<<"YES\n";
}
}
int main() {
int t;
cin>>t;
while(t--){
solve();
}
}
//易分析到如果存在两个不满足的就无解(严谨些的证明就是,假设abc,ab不足,c无限,那么ab的净含量永远不会变化,那么就不可能达到)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
cin>>n;
vector<int> vc(n),arr(n);
int cnt=0;
for(int i=0;i<n;i++){
cin>>vc[i];
}
int no=1e9;
int huai=0;
int c=0;
for(int i=0;i<n;i++){
cin>>arr[i];
if(arr[i]<=vc[i]){
no=min(vc[i]-arr[i],no);
}else{
cnt+=arr[i]-vc[i];
c++;
}
}
if(no>=cnt&&c<=1){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
int main() {
int t;
cin>>t;
while(t--){
solve();
}
}
//观察样例发现沿着路线走可以确保每次更新的时候都至少有一行或者一列只缺
//一个值,所以直接构造零发现,简单证明发现可以构造出0;(更严谨的:对于//每行列和设为s,那么ns==ms,题目设置n不一定等于m,所以此时s必须等于0)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<vector<ll>> g(n, vector<ll>(m, 0));
vector<ll> h(n, 0);
vector<ll> l(m, 0);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> g[i][j];
h[i] += g[i][j];
l[j] += g[i][j];
}
}
int x = 0, y = 0;
ll X = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] == 'R') {
g[x][y] = X - l[y];
h[x] += g[x][y];
l[y] = X;
y++;
}
else if(s[i] == 'D') {
g[x][y] = X - h[x];
l[y] += g[x][y];
h[x] = X;
x++;
}
}
g[x][y] = X - l[y];
h[x] += g[x][y];
l[y] = X;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cout << g[i][j] << " ";
}
cout << "\n";
}
}
int main() {
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}