A.2026(个人难度评价:洛谷红)
枚举模拟即可,如果数据范围较大可以使用数位dp
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
void solve(){
cout<<287926;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
B.不等式(个人难度评价:洛谷橙)
把能填的先填了,第一行后四个只能填2345或者1234,但是前者会使第4列有重复,所以第一***定为51234;
由此,(2,5)位置的数要大于4,所以只能填5,(3,5)不能填3,而第5列只剩下2,3可以填,所以(3,5)填2,(4,5)填3;
至此,(3,4)要满足大于2,而第三行3已经有有了,并且第4列4存在了,所以(3,4)只能填5;
(3,2)要满足大于(4,2),而第3行只剩1和4没被填,所以(3,2)只能填4,(3,3)填1;
(4,2)只剩2和5可以填,因为要满足小于4,所以(4,2)填2,(5,2)填5;
第5行只剩3和2没填,因为第3列已经填了2,所以只能(5,1)填2,(5,3)填3;
第3列还剩4和5没被填,但是第二行5被填了,所以(2,3)填4,(4,3)填5;
第二行还剩1和2没有填,因为第一列已经填过2了,所以(2,1)填1,(2,4)填2,
剩下两个空直接填入列没填过的数就完成了 答案:5123413425341524251325341
C.字典序(个人难度评价:洛谷橙)
cmp函数按照题意写出即可 时间复杂度:O(26nlog(n))
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
//#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
//const int inv2=500000004;
const db eps=1e-6;
//const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
struct node{
int cnt[26];
string s;
}a[N];
bool cmp(node n1,node n2){
for(int i=0;i<26;i++){
if(n1.cnt[i]!=n2.cnt[i]){
return n1.cnt[i]>n2.cnt[i];
}
}
return n1.s<n2.s;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].s;
memset(a[i].cnt,0,sizeof(a[i].cnt));
for(auto c:a[i].s){
a[i].cnt[c-'a']++;
}
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
cout<<a[i].s<<" ";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
D.括号序列(个人评价:洛谷橙)
用flag记录当前是否已经有'(',用t记录当前'('后的子串,直到遇到')'就计算子串并清空,每次遇到'('需要把子串清空 时间复杂度:O(n)
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
void solve(){
string s;
cin>>s;
string t="";
int flag=0;
int ans=0;
for(auto c:s){
if(c=='('){
flag=1;
t="";
}else if(c==')'&&flag){
int sum=0;
int now=0;
for(auto ch:t){
if(ch=='.'){
sum+=now;
now=0;
}else{
now=now*10+(ch-'0');
}
}
sum+=now;
ans=max(ans,sum);
t="";
flag=0;
}else if(flag){
t+=c;
}
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
E.矩阵旋转(个人评价:洛谷黄)
发现d<=10,所以想到可以正难则反,倒着做时原来的顺时针旋转操作要改成逆时针,逆时针同理,计算出最终状态的(dx,dy)是由初始状态的那个坐标得到的 复杂度O(dq)
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
pii xuan(int xx1,int yy1,int xx2,int yy2,int op,int x,int y){
if(op==1){
return {xx1+yy2-y,yy1+x-xx1};
}else{
return {xx1+y-yy1,yy1+xx2-x};
}
}
struct node{
int op,x,y,len;
}qry[N];
void solve(){
int n;
cin>>n;
int q;
cin>>q;
for(int i=1;i<=q;i++){
int op,x,y,len;
cin>>op>>x>>y>>len;
qry[i]={op,x,y,len};
}
int d;
cin>>d;
for(int i=1;i<=d;i++){
int x,y;
cin>>x>>y;
for(int j=q;j>=1;j--){
auto[op,xx1,yy1,len]=qry[j];
int xx2=xx1+len-1;
int yy2=yy1+len-1;
if(x<xx1||x>xx2||y<yy1||y>yy2)continue;
auto f=xuan(xx1,yy1,xx2,yy2,op,x,y);
x=f.first;
y=f.second;
}
cout<<(x-1)*n+y<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
F.能量核心(个人评价:洛谷绿)
按位贪心,我们希望高位尽量存在于答案中.
所以对于每一位,若a[i]中当前位为1,我们尝试在b数组中加入当前位,对于b数组我们利用dp求出最大的能量区段数,使得每一个能量区段的当前异或值相等.
如果能量区段数>=m并且和m的奇偶性相同,那么合法,因为多出的偶数个能量区段的异或是零,把这偶数个能量区段并到一个能量区段就行了.
如果当前位合法,我们就得把b数组加入的当前位保留并更新ans,因为高位的优先级总是高于低位的,如果当前位不合法,我们就把当前位在b数组的操作撤销
时间复杂度O(30nlog(n))
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
int a[N];
int b[N];
int dp[N];
int pre[N];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=0;
for(int i=30;i>=0;i--){
map<int,int>mp;
map<int,int>vis;
vis[0]=1;
mp[0]=0;
int tmp=ans+(1<<i);
for(int j=1;j<=n;j++){
if(a[j]>>i&1)b[j]^=(1<<i);
}
for(int j=1;j<=n;j++){
pre[j]=(pre[j-1]^b[j]);
if(vis[pre[j]^tmp]){
dp[j]=dp[mp[pre[j]^tmp]]+1;
if(dp[j]>dp[mp[pre[j]]]){
mp[pre[j]]=j;
vis[pre[j]]=1;
}
}else{
dp[j]=0;
}
}
// if(i==2){
// cout<<"test: "<<dp[n]<<'\n';
// }
if(dp[n]%2==m%2&&dp[n]>=m){
ans+=(1<<i);
}else{
for(int j=1;j<=n;j++){
if(b[j]>>i&1)b[j]-=(1<<i);
}
}
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
G.字符串(个人评价:洛谷绿)
我们使用dp,dp[i]定义为以i为结尾的合法分割的最小分割次数.
我们发现合法的分割是存在范围的,若s[i,j]已经为合法子串(不是交替串并且长度<=k),那么s[i-1,j]在长度<=k的情况下必定是合法子串,因为他已经不可能是交替串了.
所以我们可以二分出对于结尾为j,最大的下标i,使得s[i,j]不是交替串,判断交替串可以使用奇数下标前缀和和偶数下标前缀和,当前的奇数下标的值之和为0且当前的偶数下标的值之和为偶数下标的数量,或者反之,都是交替串,再加上k的限制,我们找到了可以分割的范围[l,r].
利用单点修改,区间查询的线段树,我们可以得到当前合法分割的最小值 dp[j]=min(dp[l-1],....,dp[r-1])+1
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e5+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
int tr[N<<2];
int ls(int p){
return p*2;
}
int rs(int p){
return p*2+1;
}
void pushup(int p){
tr[p]=min(tr[ls(p)],tr[rs(p)]);
}
void build(int p,int s,int t){
if(s==t){
tr[p]=0;
return;
}
int mid=(s+t)>>1;
build(ls(p),s,mid);
build(rs(p),mid+1,t);
pushup(p);
}
void update(int p,int s,int t,int l,int r,int x){
if(l<=s&&t<=r){
tr[p]=x;
return;
}
int mid=(s+t)>>1;
if(l<=mid){
update(ls(p),s,mid,l,r,x);
}
if(mid+1<=r){
update(rs(p),mid+1,t,l,r,x);
}
pushup(p);
}
int query(int p,int s,int t,int l,int r){
if(l<=s&&t<=r){
return tr[p];
}
int mid=(s+t)>>1;
int ans=inf;
if(l<=mid){
ans=min(ans,query(ls(p),s,mid,l,r));
}
if(mid+1<=r){
ans=min(ans,query(rs(p),mid+1,t,l,r));
}
return ans;
}
int pre[N];
string s;
int check(int l,int r){
int len=r-l+1;
int lenji=len-len/2;
int lenou=len/2;
int sji=pre[r]-pre[r-(lenji-1)*2]+(s[r-(lenji-1)*2]-'0');
int sou=pre[r-1]-pre[r-1-(lenou-1)*2]+(s[r-1-(lenou-1)*2]-'0');
if(sji==lenji&&sou==0||sji==0&&sou==lenou)return 1;
else return 0;
}
void solve(){
int n,k;
cin>>n>>k;
cin>>s;
s='!'+s;
pre[1]=s[1]-'0';
for(int i=2;i<=n;i++){
pre[i]=pre[i-2]+(s[i]-'0');
}
build(1,1,n);
update(1,1,n,1,1,1);
for(int i=2;i<=n;i++){
int l=1,r=i-1,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid,i)){
r=mid-1;
}else{
ans=mid;
l=mid+1;
}
}
int dp=query(1,1,n,i-1,i-1)+1;
if(ans!=-1){
int l=max(1ll,i-k+1),r=ans;
if(l<=r){
if(l==1){
dp=1;
}else{
dp=min(dp,query(1,1,n,l-1,r-1)+1);
}
}
}
update(1,1,n,i,i,dp);
}
cout<<query(1,1,n,n,n)-1<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
H.星海(个人评价:洛谷绿)
可以想到用最短路求解,瓶颈在于无法确定源点,所以我们使用次短路,因为对于一个计划星球来说到达它的最短路肯定是自己,所以次短路就是这个点到达别处星球的最小值(只要钦定一个点的次短路和最短路的出发点不同即可)
时间复杂度O(nlogn)
比较相似的一道题:2025浙江省赛F
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e5+10;
const int base=499;
int dcmp(double x){
if(fabs(x)<eps){
return 0;
}
return x<0?-1:1;
}
void debug(){
cout<<"Test:Wrong"<<'\n';
exit(0);
}
int dis[N][2];
int st[N][2];
int vis[N][2];
int b[N];
vector<pii>g[N];
struct node{
int s,x,w,id;
bool operator<(node p)const{
return w>p.w;
}
};
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
g[i].clear();
dis[i][0]=inf;
dis[i][1]=inf;
st[i][0]=-1;
st[i][1]=-1;
vis[i][0]=0;
vis[i][1]=0;
}
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
g[x].push_back({y,w});
g[y].push_back({x,w});
}
int k;
cin>>k;
priority_queue<node>q;
for(int i=1;i<=k;i++){
cin>>b[i];
q.push({b[i],b[i],0,0});
dis[b[i]][0]=0;
st[b[i]][0]=b[i];
}
while(q.size()){
auto[s,x,w,id]=q.top();
q.pop();
if(vis[x][id])continue;
vis[x][id]=1;
for(auto [y,d]:g[x]){
if(dis[y][0]>dis[x][id]+d){
dis[y][1]=dis[y][0];
dis[y][0]=dis[x][id]+d;
st[y][1]=st[y][0];
st[y][0]=s;
q.push({st[y][0],y,dis[y][0],0});
q.push({st[y][1],y,dis[y][1],1});
}else if(s!=st[y][0]&&dis[y][1]>dis[x][id]+d){
dis[y][1]=dis[x][id]+d;
q.push({st[y][1],y,dis[y][1],1});
}
}
}
int ans=inf;
for(int i=1;i<=k;i++){
ans=min(ans,dis[b[i]][1]);
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
京公网安备 11010502036488号