# 2022.5.9-1

Ideas ： We can know that the problem is equivalent to the shortest path problem ,bfs that will do .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
char mp[105][105];
int len[105];
signed main()
{

memset(len,0x3f,sizeof(len));
int n;cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];
queue<pair<int,int>> q;
q.push({
1,0});
while(q.size())
{

auto now=q.front();
q.pop();
for(int i=1;i<=n;i++)
{

if(mp[now.first][i]=='N')
continue;
if(len[i]<=now.second+1)
continue;
len[i]=now.second+1;
q.push({
i,len[i]});
}
}
if(len[2]==0x3f3f3f3f3f3f3f3f)
cout<<-1<<endl;
else
cout<<len[2]-1<<endl;
}



# 2022.5.9-2

Ideas ： greedy , Walk past every gas station without refueling , Put the amount of fuel that can be added into the priority queue , When the fuel is insufficient for the next gas station at a certain time, greedily select the maximum fuel in the queue to join .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
priority_queue<int> pq;
struct P
{

int a,b;
bool operator<(const P& p)const&{

return a<p.a;
}
}pn[MAXN];
signed main()
{

int l,p,n;cin>>l>>p>>n;
for(int i=1;i<=n;i++)
cin>>pn[i].a>>pn[i].b;
pn[n+1].a=l;
sort(pn+1,pn+1+n);
int cnt=0;
for(int i=1;i<=n+1;i++)
{

while(p<pn[i].a)
{

if(pq.size()==0)
{

cout<<-1<<endl;
return 0;
}
p+=pq.top();
pq.pop();
cnt++;
}
pq.push(pn[i].b);
}
cout<<cnt<<endl;
}



# 2022.5.9-3

Ideas ： You can know that the cars in the same line must be the same color , Therefore, the cars that can be connected by ranks are directly regarded as a group , Just count how many groups there are .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
char mp[25][25];
bool delr[25],delc[25];
int n,m;
void clr(int x,int y)
{

mp[x][y]='.';
if(!delr[x])
{

delr[x]=1;
for(int i=1;i<=m;i++)
if(mp[x][i]=='R')
clr(x,i);
}
if(!delc[y])
{

delc[y]=1;
for(int i=1;i<=n;i++)
if(mp[i][y]=='R')
clr(i,y);
}
}
signed main()
{

cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{

if(mp[i][j]!='R')continue;
cnt++;
clr(i,j);
}
cout<<cnt<<endl;
}



# 2022.5.10-1

Ideas ： Simulation question , Exercise strength .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int q[30][30];
int g[30],t[30];
void mov(int x,int gp)
{

g[x]=gp;
q[gp][++t[gp]]=x;
}
signed main()
{

int n,m;cin>>n>>m;
for(int i=1; i<=n; i++)
t[i]=1,g[i]=i,q[i][1]=i;
for(int i=1; i<=m; i++)
{

string s;int a,b=0;
cin>>s>>a;
if(s=="move")
{

cin>>s>>b;
if(g[a]==g[b])continue;
}
int ga=g[a],gb=g[b],pos=0;
for(int i=1; i<=t[ga]; i++)
if(q[ga][i]==a)
pos=i;
if(s=="over")pos--;
for(int i=pos+1; i<=t[ga]; i++)
{

if(gb) mov(q[ga][i],gb);
else mov(q[ga][i],q[ga][i]);
}
t[ga]=pos;
}
for(int i=1; i<=n; i++)
{

cout<<i<<": ";
for(int j=1; j<=t[i]; j++)
cout<<q[i][j]<<' ';
cout<<endl;
}
}



# 2022.5.10-2

Ideas ： Dynamic programming , d p [ i ] [ j ] dp[i][j] Before considering i i A course , And the total time that can be spent is j j The biggest benefit of .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int dp[105][105];
int a[105][105];
signed main()
{

int n,m;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++)
{

dp[i][j]=dp[i-1][j];
for(int k=1;k<=j;k++)
dp[i][j]=max(dp[i-1][j-k]+a[i][k],dp[i][j]);
}
cout<<dp[n][m]<<endl;
}



# 2022.5.10-3

Ideas ： Two points answer , Half is the length of the cut stick .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int n,m;
int a[MAXN];
bool check(int x)
{

if(x==0)return true;
int cnt=0;
for(int i=1;i<=n;i++)
cnt+=a[i]/x;
return cnt>=m;
}
signed main()
{

cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int L=0,R=0x3f3f3f3f3f3f3f3f;
while(L<R)
{

int mid=(L+R+1)/2;
if(check(mid)) L=mid;
else R=mid-1;
}
cout<<L<<endl;
}



# 2022.5.11-1

Ideas ： greedy , If from 0 To x After sorting, it is part of an ordered array , be 0 To x The maximum value of is x, If this condition is met, this paragraph can be cut off , The following numbers are the same .

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int a[100010];
int main()
{

int n, ma = 0, ans = 0;
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
for(int i = 0; i < n; i ++)
{

ma = max(ma, a[i]);
if(i == ma)
ans ++;
}
cout << ans << endl;
return 0;
}



# 2022.5.11-2

Ideas ：bfs When you go to the next step, you can judge whether there are obstacles at this position at two time points .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
char mp[10][10];
int t[10][10];
struct P{
int x,y;};
signed main()
{

queue<P> q;
int sx=0,sy=0,tx=0,ty=0;
for(int i=1; i<=8; i++)
for(int j=1; j<=8; j++)
{

cin>>mp[i][j];
if(mp[i][j]=='M')
sx=i,sy=j;
if(mp[i][j]=='A')
tx=i,ty=j;
}
memset(t,0x3f,sizeof(t));
t[sx][sy]=0;
q.push({
sx,sy});
while(q.size())
{

P now=q.front();
q.pop();
for(int i=-1; i<=1; i++)
for(int j=-1; j<=1; j++)
{

int nx=now.x+i,ny=now.y+j,nt=t[now.x][now.y]+1;
if(nx<1||nx>8||ny<1||ny>8)continue;
if(nx-nt+1>=1&&mp[nx-nt+1][ny]=='S')continue;
if(nx-nt>=1&&mp[nx-nt][ny]=='S')continue;
if(nt>=t[nx][ny])continue;
q.push({
nx,ny});
t[nx][ny]=nt;
}
}
if(t[tx][ty]==0x3f3f3f3f3f3f3f3f)
cout<<"Lost"<<endl;
else cout<<"Win"<<endl;
}



# 2022.5.11-3

Ideas ： Dynamic programming , d p [ i ] [ j ] dp[i][j] Before you think about it i i Stage , And the first i i The value of the phase is j j The number of solutions at that time . You can know d p [ i ] [ j ] dp[i][j] The result of is by ∑ k = 1 j − 1 d p [ i − 1 ] [ k ] \sum_{k=1}^{j-1}dp[i-1][k] Transfer to , The latter can be prefixed and accelerated .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
const int MOD=998244353;
int l[205],r[205];
int dp[205][10005];
int pre[205][10005];
signed main()
{

int n;cin>>n;
for(int i=1;i<=n;i++)
cin>>l[i]>>r[i];
for(int i=0;i<10005;i++)
pre[0][i]=1;
for(int i=1;i<=n;i++)
{

for(int j=l[i];j<=r[i];j++)
dp[i][j]=pre[i-1][j-1];
for(int j=1;j<10005;j++)
pre[i][j]=(pre[i][j-1]+dp[i][j])%MOD;
}
cout<<pre[n][r[n]]<<endl;
}



https://cdmana.com/2022/134/202205141349063690.html

Scroll to Top