Codeforces Round #744 (Div. 3)题解

A - Casimir’s String Solitaire

#include
using namespace std;
string s;
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int a=0,b=0,c=0;cin>>s;
		for(int j=0;j 
B - Shifting Sort
 
#include
using namespace std;
int t,n;const int N=55;
int a[N];
vector> v;
pair p[N];
int main(){
    scanf("%d",&t);
    while(t--){
        v.clear();
        scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            int maxi=-1e9-5,pos;
            for(int j=1;j<=n-i+1;j++){
                if(maxi
 
C - Ticks
 
#include
using namespace std;
const int N=50;
char ch[N][N];
int t,n,m,k,vis[N][N];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&k);
		memset(vis,0,sizeof vis);
		for(int i=1;i<=n;i++){
			cin>>ch[i]+1;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(ch[i][j]=='*'){
					int x=i,y=j,xx=i,yy=j;
					vector> v;
					while(x>0&&y>0&&xx>0&&yy<=m){
						if(ch[x][y]==ch[xx][yy]&&ch[x][y]=='*'){
//							vis[x][y]=vis[xx][yy]=1;
//							cout<=k){
						for(int k=0;k 
D - Productive Meeting
 
#include
using namespace std;
const int N=2e5+10;
struct node{
	int num,id;
	bool operator < (const node &a)const
    {
    	if(num==a.num) return id q;
int t,n;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		while(q.size()) q.pop();
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			if(x>=1)
			q.push({x,i});
		}
		vector< pair > v;
//		v.push_back({1,0});
		while(q.size()>=2){
			auto tp1=q.top();q.pop();
			auto tp2=q.top();q.pop();
			int x=tp1.id,y=tp2.id;
			v.push_back( {x,y} );
			if(tp1.num-1>0) q.push({tp1.num-1,tp1.id});
			if(tp2.num-1>0) q.push({tp2.num-1,tp2.id});
		}
		cout< 
E1 - Permutation Minimization by Deque
 
#include
using namespace std;
const int N=2e5+10;
int t,n,a[N],pos[N],vis[N];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) vis[i]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			pos[a[i]]=i;
		}
		int pre=n;
		vector> v;
		for(int i=1;i<=n;i++){
			int l=pos[i],r=pre;
			if(vis[i]==1) continue;
			v.push_back({l,r});
			for(int j=l;j<=r;j++) vis[a[j]]=1;
			pre=l-1;
		}
		for(int i=0;i=0;i--){
			int l=v[i].first,r=v[i].second;
			for(int j=l+1;j<=r;j++){
				printf("%d ",a[j]);
			}
		}
		cout< 
E2 - Array Optimization by Deque
 
#include
using namespace std;
const int N=2e5+10;
struct BIT{
    int n,c[N];//n为所维护的bit的范围，注意不要混用，离散化时会改变范围
    void init(int _n){n=_n;for(int i=1;i<=n;++i) c[i]=0;}
    int lowbit(int x){return x&(-x);}//负数为对应正数二进制保留最低位1及之前的0不变，其它取反 故该操作可获得x最位为1对应的值（2的几次方）
    int get_sum(int k){int ans=c[k];while((k-=lowbit(k))>0) ans+=c[k];return ans;}
    void add(int t,int v){c[t]+=v;while((t+=lowbit(t))<=n) c[t]+=v;}
}bit1;
int t,n,a[N];vector v;
map mp;
int main(){
	scanf("%d",&t);
	while(t--){
		v.clear();mp.clear();
		scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),v.push_back(a[i]);
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		for(int i=0;i 
F - Array Stabilization (AND version)
 
#include
using namespace std;
const int N=1e6+10;
int t,n,d,a[N];
int main(){
	scanf("%d",&t);
	while(t--){
//		memset(cnt,0,sizeof cnt);
		scanf("%d%d",&n,&d);
		queue> q;
		for(int i=0;i