生成一种排列，但排列不能升序
不能是升序的原因，因为(a_i≠i),而序列全是都是唯一值，升序存在一种可能1，2，3，…,n 此时(a_i=i)
这里提供一种解法
第n位为1,其余为i+1
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;const int maxn=1e3+10;
int t;
int a[maxn];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;++i){ if(i!="n)cout<<i+1<<"" "; else cout<<"1"<<endl; } }return 0; < code></=n;++i){></iostream></cstring></cstdio>
像走迷宫，先把上下左右走的操作表示出来
现在，哪个数字（0∼3）对应哪种行动（上下左右）还未分配。
即要求我们把它分配了，再按照指令走
分配就可以考虑用全排列，把上下左右按照去全排列的数字分配
上 下 左 右
上 左 下 右
…….
右 左 下 上
每个都试一遍，能到达的，++ans
注意不能走出界和路上遇到障碍
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
string s;
int n,m;
int t;const int maxn=1e3;
int nx[5],ny[5];
int tx[5]={1,-1,0,0},ty[5]={0,0,1,-1};//表示上下左右
bool mp[maxn][maxn];
int ans=0;
int pl[5],book[5];
int sx,sy,ex,ey;
void dfs(int len){
if(len==4){//排列完毕
for(int i=0;i<len;++i){ 分配操作 nx[i]="tx[pl[i]];" ny[i]="ty[pl[i]];" } int xt="sx,yt=sy;" lens="s.length();" for(int i="0;i<lens;++i){//按照指令" xt+="nx[s[i]-'0'];" yt+="ny[s[i]-'0'];" if(mp[xt][yt]) return ; 遇到障碍 if(yt<1 || xt<1>n || yt>m) return ;//出界
if(xt==ex && yt==ey){//达到终点
++ans;return ;
}
}
return ;
}
for(int i=0;i<4;++i){ 全排列 if(book[i]) continue; book[i]="1;pl[len]=i;" dfs(len+1); } int main(){ cin>>t;
while(t--){ans=0;
cin>>n>>m; memset(mp,0,sizeof(mp));
for(int i=1;i<=n;++i) for(int j="1;j<=m;++j){" char c;cin>>c;
if(c=='#') mp[i][j]=1;
if(c=='S') sx=i,sy=j;//记录起点
if(c=='E') ex=i,ey=j;//记录终点
}
cin>>s;
dfs(0);
cout<<ans<<endl; } return 0; < code></ans<<endl;></=n;++i)></4;++i){></len;++i){></iostream></cstring></cstdio>
第一步
如果有环，那么环上的字母就会无限出现，那么权值将会无穷大
所以第一步先判断有没有 环,注意是有向图，所以可以考虑用拓扑排序
第二步
根据题中给的要求，出现频率最高的 字母
注意是字母！像遇到二进制和字母，都可以尝试枚举（一般出题人都不会卡你
我们把每个字母枚举，然后求出现枚举的这个字母的最大路权值即可
枚举时，我们把枚举的字母的点的权值设为1，其他为0
根据前面拓扑排序后，没有环，所以可以用dp
(为什么可以用，因为是有向图且没有环，天然满足dp的无后效性原则)
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
const int maxn=3e5+10;
int head[maxn];
int f[maxn];
struct node{
int v,next;
}e[maxn];
string s;
int cnt=0;
void add(int u,int v){
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int q[maxn];
int in[maxn];//入度
bool topsort(){
int l=1,r=0;
for(int i=1;i<=n;++i) if(in[i]="=0)" q[++r]="i;" while(l<="r){" int u="q[l];" for(int i="head[u];i;i=e[i].next){" v="e[i].v;in[v]--;" if(in[v]="=0)" }++l; } if(r="=n)" return 0; 1; main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m;
cin>>s;
for(int i=1;i<=m;++i){ int u,v;cin>>u>>v;
add(u,v);++in[v];
}
int res=0;
if(topsort()) puts("-1");//有环图
else {
for(char c='a';c<='z';++c){ for(int i="1;i<=n;++i)//初始化" if(in[i]="=0)" f[i]="s[i-1]==c;" int u="q[i];" j="head[u];j;j=e[j].next){" v="e[j].v；" w="s[v-1]==c;" f[v]="max(f[v],w+f[u]);" res="max(res,f[v]);" } cout<<res<<endl; return 0; < code></='z';++c){></=m;++i){></=n;++i)></iostream></cstring></cstdio>
Original: https://www.cnblogs.com/guiyou/p/15170555.html
Author: 归游
Title: AcWing 第13场周赛
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584602/
转载文章受原作者版权保护。转载请注明原作者出处！