TMD这篇博客之前写了三四十分钟
然后一交
网络连接错误
非常感动所以你们看到的是第二版
（下次提交之前一定要先保存！！！）
写的简略点，就是一直没写的前几天我FST的那场CF题解
开场D然而D题FST也是非常感动
记忆化搜索
好像贪心也可以过的样子
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
int Ans=0,a1,a2;
int f[1005][1005];
void DFS(int a,int b,int val){
if (f[a][b]>=val) return;
Ans=max(Ans,val);
f[a][b]=val;
if (a==0||b==0) return;
if (b>=2) DFS(a+1,b-2,val+1);
if (a>=2) DFS(a-2,b+1,val+1);
}
int main(){
a1=IN(),a2=IN();
memset(f,128,sizeof f);
DFS(a1,a2,0);
printf("%d\n",Ans);
}
维护一个指针从左往右扫
具体看代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
int a[1005];
bool vis[1005];
int main(){
int n=IN();
Rep(i,1,n) a[i]=IN();
sort(a+1,a+n+1);
int Ans=0,now=1;
Rep(i,1,n){
now++;
while (now<=n&&a[now]<=a[i]) now++;
if (now<=n) Ans++;else break;
}
printf("%d\n",Ans);
}
按X坐标排序后加一下
按Y坐标排序后加一下
再减掉XY都一样的
注意要开LL 然而我肯定开
因为以前三题FST都是死在LL上非常感动
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
struct Node{
int x,y;
}a[200005];
int n;
bool cmp1(const Node&a,const Node&b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmp2(const Node&a,const Node&b){return a.y==b.y?a.x<b.x:a.y<b.y;}
int main(){
n=IN();
Rep(i,1,n) a[i].x=IN(),a[i].y=IN();
ll Ans=0;
sort(a+1,a+n+1,cmp1);
Rep(i,1,n){
int j=i;
while (j<=n&&a[i].x==a[j].x) j++;j--;
Ans+=1ll*(j-i+1)*(j-i)/2;
i=j;
}
sort(a+1,a+n+1,cmp2);
Rep(i,1,n){
int j=i;
while (j<=n&&a[i].y==a[j].y) j++;j--;
Ans+=1ll*(j-i+1)*(j-i)/2;
i=j;
}
Rep(i,1,n){
int j=i;
while (j<=n&&a[i].x==a[j].x&&a[i].y==a[j].y) j++;j--;
Ans-=1ll*(j-i+1)*(j-i)/2;
i=j;
}
printf("%I64d\n",Ans);
}
非常感动
开场刚D 喔喔喔感觉好吊啊这题
然后想了想发现
不就三种吗
直接往左，直接往右，先右再左
然后愉快地PP了
然后就愉快地FST了
因为可以先左在右 我TM怎么会没想到 GG
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=500005;
ll c[N],p[N],s[N];
ll n,a,b,T;
char S[N];
int main(){
n=IN(),a=IN(),b=IN(),T=IN();
gets(S+1);
Rep(i,1,n) if (S[i]=='w') c[i]=b+1; else c[i]=1;
if (c[1]>T) return puts("0"),0;
p[1]=c[1];Rep(i,2,n) p[i]=p[i-1]+c[i];
s[n]=c[n];Drp(i,n-1,1) s[i]=s[i+1]+c[i];
ll Ans=0,z1=1,z2=n;
while (z1<=n&&p[z1]+(z1-1)*a<=T) z1++;Ans=z1-1;
while (z2>=2&&c[1]+s[z2]+(n+1-z2)*a<=T) z2--;Ans=max(Ans,n-z2+1);
Rep(i,2,n){
while (z2<=i||p[i]+(2*i-1+n-z2)*a+s[z2]>T) z2++;
Ans=max(Ans,i+n-z2+1);
}
Drp(i,n,2){
while (z1>=i||s[i]+(2*(n-i+1)+z1-1)*a+p[z1]>T) z1--;
Ans=max(Ans,z1+n-i+1);
}
printf("%d\n",Ans);
}
把每行每列排序一下 然后首先把每行每列权值相同的连边
Tarjan缩一下点
然后再每个点向同一行同一列只比它大的那个点连一下边
拓扑排序一下就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=1000005;
struct Poi{
int val,idx;
bool operator <(const Poi&x)const{return val<x.val;}
}a[N];
vector<Poi>ac[N],ar[N];
int Ans[N],n,m;
int id(int a,int b){return (a-1)*m+b;}
int to[N*4],next[N*4],head[N],cnt,rd[N];
void AddEdge(int u,int v){
to[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
int ins[N],dfn[N],low[N],T,Top,s[N],IDX;
void Tarjan(int u){
dfn[u]=low[u]=++T;
ins[u]=1;s[++Top]=u;
Cross(i,u){
if (!ins[to[i]]){
Tarjan(to[i]);
low[u]=min(low[u],low[to[i]]);
}
else if (ins[to[i]]==1) low[u]=min(low[u],dfn[to[i]]);
}
if (dfn[u]==low[u]){
++IDX;
while (s[Top]!=u) rd[s[Top--]]=IDX;
rd[s[Top--]]=IDX;
}
ins[u]=2;
}
int q[N],h,t,lt[N];
void Topo(){
while (h<=t){
int u=q[h++];
Cross(i,u){
Ans[to[i]]=max(Ans[to[i]],Ans[u]+1);
lt[to[i]]--;
if (!lt[to[i]]) q[++t]=to[i];
}
}
}
int main(){
n=IN(),m=IN();
Rep(i,1,n) Rep(j,1,m){
a[id(i,j)].val=IN(),a[id(i,j)].idx=id(i,j);
ac[i].push_back((Poi){a[id(i,j)].val,a[id(i,j)].idx});
ar[j].push_back((Poi){a[id(i,j)].val,a[id(i,j)].idx});
}
Rep(i,1,n) sort(ac[i].begin(),ac[i].end());
Rep(i,1,m) sort(ar[i].begin(),ar[i].end());
cnt=0;memset(head,-1,sizeof head);
Rep(i,1,n) Rep(j,0,m-2)
if (ac[i][j].val==ac[i][j+1].val)
AddEdge(ac[i][j].idx,ac[i][j+1].idx),
AddEdge(ac[i][j+1].idx,ac[i][j].idx);
Rep(i,1,m) Rep(j,0,n-2)
if (ar[i][j].val==ar[i][j+1].val)
AddEdge(ar[i][j].idx,ar[i][j+1].idx),
AddEdge(ar[i][j+1].idx,ar[i][j].idx);
Rep(i,1,n*m) if (!rd[i]) Tarjan(i);
cnt=0;memset(head,-1,sizeof head);
Rep(i,1,n) Rep(j,0,m-2)
if (ac[i][j].val<ac[i][j+1].val)
AddEdge(rd[ac[i][j].idx],rd[ac[i][j+1].idx]),lt[rd[ac[i][j+1].idx]]++;
Rep(i,1,m) Rep(j,0,n-2)
if (ar[i][j].val<ar[i][j+1].val)
AddEdge(rd[ar[i][j].idx],rd[ar[i][j+1].idx]),lt[rd[ar[i][j+1].idx]]++;
h=1,t=0;
Rep(i,1,IDX) if (!lt[i]) q[++t]=i,Ans[i]=1;
Topo();
Rep(i,1,n){
Rep(j,1,m) printf("%d ",Ans[rd[id(i,j)]]);
puts("");
}
}
Aug 27, 2023 08:03:22 PM
NCERT Exemplar is very Important Resource for Students Preparing for 10th Class Examination 2024, Here we have Provided NCERT Class 10 Exemplar Problems Solutions 2024, Sometimes, people confuse NCERT Exemplar Problems NCERT Exemplar Solutions for 10th Class 2024 Solutions with CBSE Solutions, There are Some Solutions which NCERT itself Prescribes, You can check those NCERT Exemplar Problems 2024 here, This Page also Provide NCERT 10th Exemplar for 10 Class, NCERT Students you can Subject Wise Pdf Download at Official Website at,Here you will get the NCERT Class 10 Exemplar Problems.