A
题中所给的x是一个质数，所以将序列a中的数分解质因数，开一个动态数组二维prime，如果a[i]能被质数x整除则将i加入到数组prime[x]末端，查询时二分左右边界即可
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
void solve()
{
vector<vector<int>>prime(100001);
int n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
for(int j=2;j*j<=x;j++)
if(x%j==0)
{
prime[j].pb(i);
while(x%j==0) x/=j;
}
if(x>1)
prime[x].pb(i);
}
int m,l,r;
cin>>m;
while(m--)
{
cin>>l>>r>>x;
int lc=0,rc=prime[x].size()-1,pos1=-1;
while(lc<=rc)
{
int mid=(lc+rc)/2;
if(prime[x][mid]>=l)
{
rc=mid-1;
pos1=mid;
}
else
lc=mid+1;
}
if(pos1==-1)
{
cout<<"666666!\n";
continue;
}
int pos2=-1;
lc=0,rc=prime[x].size()-1;
while(lc<=rc)
{
int mid=(lc+rc)/2;
if(prime[x][mid]<=r)
{
lc=mid+1;
pos2=mid;
}
else
rc=mid-1;
}
if(pos2>=pos1)
cout<<pos2-pos1+1<<'\n';
else
cout<<"666666!\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
B
看用例找规律
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define fi first
#define se second
const int N=6e5+5,mod=1e9+7,INF=0x3f3f3f3f;
const double pi=acos(-1.0),E=exp(1);
void solve()
{
ll n;
cin>>n;
cout<<n*(n+1)/2<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
C
数k只能由1到k-1移动到k的位置上，考虑从前往后遍历，记录下每个数的位置，首先将1的上下左右标记上，从2到n*m遍历，遍历到数i时，如果该数的位置未被标记则说明无法移动到该数上，输出NO并返回，否则将i的上下左右位置标记上，表示为可以到达，继续判断下一个数
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define fi first
#define se second
const int N=6e5+5,mod=1e9+7,INF=0x3f3f3f3f;
const double pi=acos(-1.0),E=exp(1);
int n,m;
int a[105][105],vis[105][105];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void solve()
{
cin>>n>>m;
int x,y;
pair<int,int>pos[N];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
vis[i][j]=0;
if(a[i][j]==1)
{
x=i;
y=j;
}
pos[a[i][j]]={i,j};
}
vis[x][y]=1;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<0||xx>n||yy<0||yy>m||vis[xx][yy])
continue;
vis[xx][yy]=1;
}
for(int i=2;i<=n*m;i++)
{
auto [x,y]=pos[i];
if(!vis[x][y])
{
cout<<"NO\n";
return ;
}
for(int j=0;j<4;j++)
{
int xx=x+dx[j],yy=y+dy[j];
if(xx<0||xx>n||yy<0||yy>m||vis[xx][yy])
continue;
vis[xx][yy]=1;
}
}
cout<<"YES\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
D
并查集，fa[x]表示从x开始右边第一个没学过的算法的位置，具体操作是对于每一次的[l,r],都从l右边第一个没学的算法开始，并将这个没学的算法合并到r右边第一个没学的算法上，再跳到右边第一个没学的算法上并ans++。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e6+5;
#define pb push_back
int fa[N];
int find(int x)//并查集
{
return fa[x]==x? x:fa[x]=find(fa[x]);
}
void solve()
{
int n,m,r,l;
cin>>n>>m;
for(int i=1;i<=n+1;i++)
fa[i]=i;
while(m--)
{
cin>>l>>r;
int ans=0;
for(int i=find(l);i<=r;i=find(i+1))
{
fa[find(i)]=find(r+1);
ans++;
}
cout<<ans<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
E
区间修改，区间查询，考虑线段树，对于操作f可以先预处理数组中每一个数的二进制表示，每次操作时去最高位，操作g就是一个x+lowbit(x)操作，当x等于2的q（q为非负整数）次方时（二进制表示下只有一个1），该操作退化为x*2，对于两种操作可以先暴力更改，当一区间的数均可表示为2的q（q为非负整数）次方时，标记该区间，对于被标记的区间操作1直接将该区间的权值改为0即可，操作2则将该节点的权值和记账本均乘以2
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define fi first
#define se second
#define lc p<<1
#define rc p<<1|1
const int N=2e5+5,mod=998244353,INF=0x3f3f3f3f;
struct node{
int l,r;
bool fign;
ll add,sum;
}tr[N*4];
ll a[N];
vector<vector<int>>g(N);
void pushup(int p){//向上更新，该节点的权值等于左右子树的权值相加，如果左右子树均被标记则该节点也要标记
tr[p].sum=tr[lc].sum+tr[rc].sum;
if(tr[lc].fign&&tr[rc].fign) tr[p].fign=1;
else tr[p].fign=0;
}
int lowbit(int x)
{
return x&(-x);
}
void f(int p,int c)
{
tr[p].sum*=c;
tr[p].sum%=mod;
tr[p].add*=c;
tr[p].add%=mod;
}
void pushdown(int p){//向下更新
if(tr[p].add!=1)//将记账本上的数传递给子树
{
f(lc,tr[p].add);
f(rc,tr[p].add);
tr[p].add=1;
}
}
void build(int p,int l,int r)//建树
{
tr[p]={l,r,0,1,a[l]};
if(l==r)
{
tr[p].fign=(lowbit(a[l])==a[l]);
return ;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
void updata2(int p,int x,int y)
{
if(x<=tr[p].l&&y>=tr[p].r&&tr[p].fign)//如果区间覆盖且被标记该节点权值与记账本均乘以2
{
tr[p].sum*=2;
tr[p].add*=2;
tr[p].sum%=mod;
tr[p].add%=mod;
return ;
}
if(tr[p].l==tr[p].r)//该节点表示单个点时进行操作2并判断该点是否要被标记
{
tr[p].sum+=lowbit(tr[p].sum);
if(tr[p].sum==lowbit(tr[p].sum))
tr[p].fign=1;
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(x<=mid)updata2(lc,x,y);
if(y>mid) updata2(rc,x,y);
pushup(p);
}
void updata1(int p,int x,int y)
{
if(tr[p].sum==0) return ;
if(tr[p].l==tr[p].r)
{
if(tr[p].fign)
tr[p].sum=0;
else
{
int x=g[tr[p].l].back();
g[tr[p].l].pop_back();
tr[p].sum-=(1<<x);
}
if(lowbit(tr[p].sum)==tr[p].sum) tr[p].fign=1;
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(x<=mid)updata1(lc,x,y);
if(y>mid) updata1(rc,x,y);
pushup(p);
}
ll query(int p,int x,int y)
{
if(x<=tr[p].l&&y>=tr[p].r)
return tr[p].sum%mod;
int mid=(tr[p].l+tr[p].r)>>1;
pushdown(p);
ll sum=0;
if(x<=mid)sum+=query(lc,x,y);
if(y>mid)sum+=query(rc,x,y);
return sum%mod;
}
void solve()
{
int n,m,op,x,y,k;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
int x=a[i],c=0;
while(x)
{
if(x&1)g[i].pb(c);
c++;
x/=2;
}
}
build(1,1,n);
while(m--)
{
cin>>op;
if(op==1)
{
cin>>x>>y;
updata1(1,x,y);
}
else if(op==2)
{
cin>>x>>y;
updata2(1,x,y);
}
else
{
cin>>x>>y;
cout<<query(1,x,y)<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
F
比较显然的是尽量使前面的数变成牛逼数是最好的操作，答案又具有单调性所以使用二分，二分操作次数，在check函数内对于序列前面的非牛逼数，如果有操作次数，如果有操作次数就使用一次操作让它变成牛逼数，记录操作完后的牛逼数数量记为cnt，返回cnt大于等于m。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define fi first
#define se second
const int N=1e5+5,mod=1e9+7,INF=0x3f3f3f3f;
const double pi=acos(-1.0),E=exp(1);
int a[N],cnt[N],vis[N];
bool check(int x,int m,int n)
{
int i,j,cnt=0;
if(x>=n)
return true;
for(i=1;i<=n;i++){
if(cnt>=a[i])
cnt++;
else if(x){
cnt++;
x--;
}
}
return cnt>=m;
}
void solve()
{
int n,m;
cin>>n>>m;
int c=0,c1=0,c2=0;
vector<int>pos[100001];
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
if(c>=a[i])
c++;
}
if(c>=m)
{
cout<<0<<'\n';
return ;
}
int l=1,r=n,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid,m,n))
{
r=mid-1;
ans=mid;
}
else
l=mid+1;
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
G
可以记录下有多少边是不能被删除的，当不存在一个k使的dis(i,j)=dis(i,k)+dis(k,j)时，该边是不可以删除的（比如有三条边A-D，A-B，B-D，权值分别为3,1,2时A-D是可以删除的）得出有多少边是不可删除后用总边数减去不可删除的边即可（改一下循环体，j从i+1开始遍历就不用除以2了）dis（最短路）用Floyd算法处理即可（虽然我搞不懂）。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
ll dis[305][305];
void solve()
{
ll n,m,u,v,w;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=1e18;
for(int i=0;i<m;i++)
{
cin>>u>>v>>w;
dis[u][v]=min(dis[u][v],w);
dis[v][u]=min(dis[v][u],w);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
int res=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int fign=1;
for(int k=1;k<=n;k++)
{
if(k!=i&&k!=j)
{
if(dis[i][j]==dis[i][k]+dis[k][j])
{
fign=0;
break;
}
}
}
res+=fign;
}
cout<<m-res<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
H
对任意，对任意开头现以每个数字为开头的序列的总数都是一样，所以K为偶数时只需先输出1个k/2，再输出n-1个k即可，即可。当K为奇数时，如果将序列长度定为n则答案为n个(k+1)/2，由于大于(n+1)/2与小于(n+1)/2的数的个数是一样的，所以就代表着这些数都有对标的比它大的数或者比它小的数所以要往前移动(n-1)/2个位置,就是中位序列。（其实我搞不懂为什么）。 移动的具体操作是将指针指向序列的最后一位，当序列的最后一位为1时序列长度减1，否则 将最后一位上的数减1，将序列长度变为n，后面的项全都变为（n+1）/2。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
void solve()
{
int n,k;
cin>>n>>k;
if(k%2==0)
{
cout<<k/2<<' ';
for(int i=1;i<n;i++)
cout<<k<<' ';
}
else
{
vector<int>ans(n+1);
for(int i=1;i<=n;i++)
ans[i]=(k+1)/2;
int t=n;
for(int i=1;i<=n/2;i++)
if(ans[t]==1)
t--;
else
{
ans[t]--;
while(t<n)ans[++t]=k;
}
for(int i=1;i<=t;i++)
cout<<ans[i]<<' ';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
I
dp: 该题与01背包的不同之处就是加了1个不能连续选指定的三个仙跳墙，所以要在01背包的基础上再加2维表示01所选序列的最后两位，dp[j][last1][last2]表示背包容量为j且最后选择的两个仙跳墙的编号为last1和last2时，得到的最大攻击。 状态转移方程为:dp[j][i][last1]=max(dp[j][i][last1],dp[j-w[i]][last1][last2]+v[i]);
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define fi first
#define se second
const int N=1e7+20,mod=1e9+7,INF=0x3f3f3f3f,p=998244353;
const double pi=acos(-1.0),E=exp(1);
ll dp[105][105][105];
void solve()
{
int n,m,t,x,y,z;
cin>>n>>t>>m;
vector<int>v(n+1),w(n+1),vis1(n+1),vis2(n+1);
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
vis1[i]=vis2[i]=-1;
}
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
vis1[z]=y;
vis2[z]=x;
}
ll ans=0;
for(int i=1;i<=n;i++)
for(int last1=0;last1<i;last1++)
for(int last2=0;last2<=last1;last2++)
{
if(vis1[i]==last1&&vis2[i]==last2)
continue;
if(last1!=last2||last1==0)
{
for(int j=t;j>=w[i];j--)
{
dp[j][i][last1]=max(dp[j][i][last1],dp[j-w[i]][last1][last2]+v[i]);
ans=max(ans,dp[j][i][last1]);
}
}
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
京公网安备 11010502036488号