F.
模拟题，不难只是比较繁琐，需要分情况讨论
debug:
如何判断永远走不到终点格？
原思路是这个点同时这个点指向的方向被经过了，那么就是走的重复的路，走不到终点
但不知为何map出了一些问题
后来看题解，只要步数很大了还走不到那么就永远走不到
于是我把map删了，过了
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,m;cin>>n>>m;
int i1,j1,i2,j2;cin>>i1>>j1>>i2>>j2;
string d;cin>>d;
int tx=i1,ty=j1;string ts=d;
// cout<<"tx="<<tx<<' '<<"ty="<<ty<<'\n';
int step=0;
int total=4*n*m+1;
while(total--) {
if (tx == i2 && ty == j2) {
cout << step << '\n';
return;
}
if (ts == "UL") {
while (1) {
if (tx == 1 && ty == 1) {
ts = "DR";
break;
} else if (tx == 1) {
ts = "DL";
break;
} else if (ty == 1) {
ts = "UR";
break;
}
tx--;
ty--;
// cout<<"tx="<<tx<<' '<<"ty="<<ty<<'\n';
if (tx == i2 && ty == j2) {
cout << step << '\n';
return;
}
//
}
} else if (ts == "UR") {
while (1) {
if (tx == 1 && ty == m) {
ts = "DL";
break;
} else if (tx == 1) {
ts = "DR";
break;
} else if (ty == m) {
ts = "UL";
break;
}
tx--;
ty++;
// cout<<"tx="<<tx<<' '<<"ty="<<ty<<'\n';
if (tx == i2 && ty == j2) {
cout << step << '\n';
return;
}
}
} else if (ts == "DL") {
while (1) {
if (tx == n && ty == 1) {
ts = "UR";
break;
} else if (tx == n) {
ts = "UL";
break;
} else if (ty == 1) {
ts = "DR";
break;
}
tx++;
ty--;
// cout<<"tx="<<tx<<' '<<"ty="<<ty<<'\n';
if (tx == i2 && ty == j2) {
cout << step << '\n';
return;
}
}
} else if (ts == "DR") {
while (1) {
if (tx == n && ty == m) {
ts = "UL";
break;
} else if (tx == n) {
ts = "UR";
break;
} else if (ty == m) {
ts = "DL";
break;
}
tx++;
ty++;
// cout<<"tx="<<tx<<' '<<"ty="<<ty<<'\n';
if (tx == i2 && ty == j2) {
cout << step << '\n';
return;
}
}
}
step++;
}
cout<<"-1"<<'\n';
}
signed main(){
int hey_left=1;
cin>>hey_left;
while(hey_left--){
solve();
}
}
G1.
可以把c数组从小到大升序，因为大数只能由比它小的数得到，所以升序不影响
把在a数组里能组成的所有和标记
遍历c数组，若当前数被标记，则满足条件，并把该数加到a数组，更新和
用了dp，从后往前遍历值域
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;cin>>n;
vector<int>c(n+1);
for(int i=1;i<=n;i++)cin>>c[i];
sort(c.begin()+1,c.end());
if(c[1]!=1){
cout<<"NO"<<'\n';
return ;
}
int dp[5010];
for(int i=0;i<5010;i++)dp[i]=0;
dp[1]=1;dp[0]=1;
for(int i=2;i<=n;i++){
int t=c[i];
if(dp[t]){
for(int j=5000;j>=t;j--){
if(dp[j-t])dp[j]=1;
}
}else{
cout<<"NO"<<'\n';
return ;
}
}
cout<<"YES"<<'\n';
}
signed main(){
int hey_left=1;
cin>>hey_left;
while(hey_left--){
solve();
}
}
G2.
我服了呀，什么诈骗题，既然是O（n）的还搞什么easy hard
放最后一题我以为很难
像这样的操作方式，可知在前缀和之间的任何数都可以得到，所以排序后直接求前缀和，再遍历判大小即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
void solve(){
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a.begin()+1,a.end());
if(a[1]!=1){
cout<<"NO"<<'\n';
return ;
}
int sum=1;
for(int i=2;i<=n;i++){
if(a[i]>sum){
cout<<"NO"<<'\n';
return ;
}
sum+=a[i];
}
cout<<"YES"<<'\n';
}
signed main(){
int hey_left=1;
cin>>hey_left;
while(hey_left--){
solve();
}
}