Problem – D – Codeforces
预处理四种字母个数的前缀和，快速得到某段区间某种字母的个数
排序有两个要求，一个是按照字母出现的次数从大到小排序，这个比较简单，一个是按照ATGC的顺序排列，这个比较棘手，我们可以采用编码的形式来解决这个问题，我们可以利用set，存入两维，第一维是字母出现的次数，第二维是该字母的编码，我们按照ATGC的顺序分别编码为3210，这样的话，放入set排序，先按照字母出现的次数从小到大排序，再按照CGTA的顺序排，那么倒过来就是我们要的答案
AC代码:
#include
#define endl 'n'
//#define int long long
using namespace std;
const int N=5e4+10;
typedef pairPII;
int preA[N],preT[N],preG[N],preC[N];
string s;
string tmp="CGTA";
int m;
void solve() {
cin>>s>>m;
mapmp;
int n=s.size();
s=' '+s;
for(int i=1;i>l>>r;
setq;
ans="";
mp['A']=preA[r]-preA[l-1];
mp['T']=preT[r]-preT[l-1];
mp['G']=preG[r]-preG[l-1];
mp['C']=preC[r]-preC[l-1];
q.insert({mp['A'],3});
q.insert({mp['T'],2});
q.insert({mp['G'],1});
q.insert({mp['C'],0});
for(auto v:q) ans=tmp[v.second]+ans;
cout>t;
while(t--) {
solve();
}
return 0;
}Problem – G – Codeforces
猜测从初始序列往后不会无限变化，会固定在某一个序列不变
于是模拟即可，当出现重复的那么且没得到最终序列，则不可能得到了
AC代码:
#include
#define endl 'n'
//#define int long long
using namespace std;
string s,ss;
void solve() {
cin>>s>>ss;
mapmp;
int ans=0;
while(1){
ans++;
if(s==ss){
服务器托管网 cout100){
coutcnt;
for(int i=0;i>t;
while(t--) {
solve();
}
return 0;
}Problem – I – Codeforces
题意是一个图，从a点到b点是最短路的路都铺路，最短路可能不止一条，不是最短路的不铺路，问不铺路的总长度
先跑一遍dijkstra，算出从a到b的最短距离，然后从a开始跑dfs，中间不要忘了剪枝，当跑到b时，如果距离和最短距离一样，那么标记走过的路径，
对于那些没走过的路径，求它们路径之和
AC代码:
#include
#define endl 'n'
//#define int long long
using namespace std;
const int N=110;
typedef pairPII;
vector>e(N);
int dist[N];
bool vis[N];
int path[N];
bool used[N][N服务器托管网];
int g[N][N];
int n,m,a,b;
int idx;
void dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[a]=0;
priority_queue,greater>q;
q.push({0,a});
while(q.size()){
auto t=q.top();
q.pop();
int ver=t.second;
if(vis[ver]) continue;
vis[ver]=true;
for(auto v:e[ver]){
int ver1=v.first,d=v.second;
if(dist[ver1]>dist[ver]+d){
dist[ver1]=dist[ver]+d;
q.push({dist[ver1],ver1});
}
}
}
}
void dfs(int x,int d){
vis[x]=true;
if(x==b&&d==dist[b]){
for(int i=1;iq) swap(p,q);
used[p][q]=true;
}
vis[x]=false;
return;
}
//剪枝,若搜到该点时还没到终点并且走过的距离已经超过最短距离了,那么这条路就没必要搜了,return表示提前结束这条路,但是结束前需要回溯
if(d>=dist[b]){
vis[x]=false;
return;
}
for(auto v:e[x]){
int ver=v.first,dd=v.second;
if(vis[ver]) continue;
path[++idx]=ver;//按顺序存储这条路走过的点
dfs(ver,d+dd);
idx--;
}
vis[x]=false;//一旦走过并标记了点x,那么一定要回溯,防止其它路走到这时不通
}
void solve() {
cin>>n>>m>>a>>b;
int res=0;
for(int i=0;i>u>>v>>w;
g[u][v]=g[v][u]=w;
res+=w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dijkstra();
memset(vis,false,sizeof vis);
path[0]=a;
dfs(a,0);
int ans=0;
for(int i=1;i>t;
while(t--) {
solve();
}
return 0;
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
