The 19th Heilongjiang Provincial Collegiate Programming Contest BDIJK
B. String
思路：连续的3个可以删掉，类似括号匹配，用栈模拟即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
string s; cin>>s;
if(s.size() < 3)
{
cout<<s<<"\n";
return 0;
}
stack<char>st;
int i = 0;
while(i < s.size())
{
if(st.size() < 2)
{
st.push(s[i]);
i++;
continue;
}
char x = st.top(); st.pop();
char y = st.top(); st.pop();
if(x == y && x == s[i])
{
i++;
}else{
st.push(y);
st.push(x);
st.push(s[i]);
i++;
}
}
if(st.size() == 0)
{
cout<<"NAN\n";
return 0;
}
string ans = "";
while(!st.empty())
{
ans += st.top();
st.pop();
}
for(int i = ans.size()-1;i >= 0; i--)
cout<<ans[i];
return 0;
}
D. Card Game
思路：因为只有2个同时是攻击会产生效果，那么其实只用考虑两个都是攻击的部分就行了，用大的打对面小的。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N],b[N];
bool cmp(ll a,ll b)
{
return a > b;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
ll n,hpa,hpb; cin>>n>>hpa>>hpb;
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
cin>>b[i];
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n);
int l = 1,r = n;
while(b[l] == -1)l++;
//先大的打它小的
bool ok = true;
for(int i = 1;i <= n; i++)
{
if(a[i] == -1 || l > r){
ok = false;
break;
}
// cout<<"a[i] = "<<a[i]<<" b[l] = "<<b[l]<<"\n";
hpa -= b[l];
hpb -= a[i];
if(hpa <= 0)
{
ok = false;
break;
}
else if(hpb <= 0)
{
break;
}
l++;
// cout<<"hpa = "<<hpa<<" hpb = "<<hpb<<"\n";
}
if(!ok)
cout<<"no\n";
else{
if(hpa > 0 && hpb > 0)
cout<<"no\n";
else cout<<"yes\n";
}
}
return 0;
}
I. This is an easy problem
思路：签到，直接算就行了
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
ll n; cin>>n;
int cnt = 0;
while(n)
{
cnt += (n&1);
n>>=1;
}
cout<<cnt<<"\n";
return 0;
}
J. Trade
思路：因为只能向下和向右走，也就是说(i+1,j)和(i,j+1)只能由(i,j)转移过来。很容易想到dp。
我们定义\(dp[i][j][0/1]\)为到(i,j)位置卖出(1)和没有卖出(0)的最大收益。最后把收益是非负数的位置赋成'.'，反之设为'#'。然后跑一个bfs即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
ll a[N][N],b[N][N],dp[N][N][2];
bool vis[N][N];
ll dist[N][N];
int dir[2][2] = {{1,0},{0,1}};
int n,m;
char c[N][N];
bool in(int x,int y)
{
return x >= 1 && x <= n && y >=1 && y <= m;
}
void bfs(int sx,int sy)
{
memset(dist,127,sizeof(dist));
dist[sx][sy] = b[sx][sy];
queue<array<int,2>>q;
q.push({sx,sy});
while(!q.empty())
{
auto [x,y] = q.front();
q.pop();
for(int i = 0;i < 2; i++)
{
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if(in(dx,dy) && !vis[dx][dy] && c[dx][dy] != '#')
{
vis[dx][dy] = true;
dist[dx][dy] = dist[x][y] + b[dx][dy];
q.push({dx,dy});
}
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
cin>>a[i][j];
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
cin>>b[i][j];
memset(dp,128,sizeof(dp));
dp[1][1][0] = dp[1][1][1] = -a[1][1]-b[1][1];
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][0]-b[i+1][j]);
dp[i+1][j][1] = max(dp[i+1][j][1],dp[i][j][0]+a[i+1][j]-b[i+1][j]);
dp[i][j+1][0] = max(dp[i][j+1][0],dp[i][j][0]-b[i][j+1]);
dp[i][j+1][1] = max(dp[i][j+1][1],dp[i][j][0]+a[i][j+1]-b[i][j+1]);
}
}
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
if(dp[i][j][1] >= 0)c[i][j] = '.';
else c[i][j] = '#';
}
}
c[1][1] = '.';
bfs(1,1);
bool ok = false;
for(int i = 1;i <= n; i++)
{
if(dist[i][m] < (1<<30))
ok = true;
}
for(int i = 1;i <= m; i++)
{
if(dist[n][i] < (1<<30))
ok = true;
}
if(ok)cout<<"YES\n";
else cout<<"NO\n";
return 0;
}
K. Puzzle
思路：只有4个数，填3种符号，直接暴力2个dfs。注意因为有优先级问题，注意分类讨论。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll A,B,C,D;
ll a,b,c,d;
ll arr[10];
int s[10];
bool vis[N];
int op[3] = {0,1,2};//+,-,*
int t[10];
set<ll>ans;
void dfs(int step)
{
if(step > 3){
// cout<<t[1]<<" "<<t[2]<<" "<<t[3]<<"\n";
ll res = 0;
if(t[1] != 2 && t[2] != 2 && t[3] != 2)
{
if(t[1] == 0)
res = a + b;
else if(t[1] == 1)
res = a - b;
if(t[2] == 0)
res = res + c;
else if(t[2] == 1)
res = res - c;
if(t[3] == 0)
res = res + d;
else if(t[3] == 1)
res = res - d;
}else{
if(t[1] == 2 && t[2] == 2 && t[3] == 2)
{
res = a*b*c*d;
}
else if(t[1] == 2 && t[2] == 2)
{
res = a*b*c;
if(t[3] == 0)
res = res + d;
else if(t[3] == 1)
res = res - d;
}
else if(t[1] == 2 && t[3] == 2)
{
res = a*b;
if(t[2] == 0)
res = res + c*d;
else if(t[2] == 1)
res = res - c*d;
}
else if(t[2] == 2 && t[3] == 2)
{
if(t[1] == 0)
res = a + b*c*d;
else if(t[1] == 1)
res = a - b*c*d;
}
else if(t[1] == 2)
{
res = a*b;
if(t[2] == 0)
res = res + c;
else if(t[2] == 1)
res = res - c;
if(t[3] == 0)
res = res + d;
else if(t[3] == 1)
res = res - d;
}
else if(t[2] == 2)
{
if(t[1] == 0)
res = a + b*c;
else if(t[1] == 1)
res = a - b*c;
if(t[3] == 0)
res = res + d;
else if(t[3] == 1)
res = res - d;
}
else if(t[3] == 2)
{
if(t[1] == 0)
res = a + b;
else if(t[1] == 1)
res = a - b;
if(t[2] == 0)
res = res + c*d;
else if(t[2] == 1)
res = res - c*d;
}
}
ans.insert(res);
// cout<<res<<"\n";
return;
}
for(int i = 0;i < 3; i++)
{
t[step] = i;
dfs(step+1);
}
}
void dfs1(int k)
{
if(k > 4)
{
a = s[1],b = s[2],c = s[3],d = s[4];
dfs(1);
return;
}
for(int i = 1;i <= 4; i++)
{
if(!vis[i])
{
vis[i] = true;
s[k] = arr[i];
dfs1(k+1);
vis[i] = false;
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>A>>B>>C>>D;
arr[1] = A,arr[2] = B,arr[3] = C,arr[4] = D;
dfs1(1);
cout<<ans.size()<<"\n";
return 0;
}