训练合集-Mind the Gap

Member :EdGrass afeng111 xishuiw

wirtten by xishuiw

暑期训练

2022-2023 ACM-ICPC Latin American Regional Programming Contest

赛时过题 DEILM

补题ACH

D.Daily Trips

签到 问什么时候需要带伞

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
void solve(){
	int n,a,b;cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		char ch1,ch2;
		cin>>ch1>>ch2;
		if(ch1=='Y'||b==0){
			cout<<"Y ";
			a--;
			b++;
		}
		else {
			cout<<"N ";
		}
		if(ch2=='Y'||a==0){
			cout<<"Y ";
			b--;
			a++;
		}
		else {
			cout<<"N ";
		}
		cout<<"\n";
	} 
}
signed main(){
	close;
	solve();
}

E.Empty Square

#include <iostream>
using namespace std;

const int N = 1007;
int vis[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k, e;
    cin >> n >> k >> e;
    vis[k] = 1;
    int l = e, r = n - k - e;
    int ans = 0;
    if (l > r)
        swap(l, r);
    if (l == 1)
    {
        if (vis[1])
            ans++;
        else
            vis[1] = 1;
    }
    else if (l == 2)
    {
        if (vis[2])
        {
            vis[1] = 1;
            ans++;
        }
        else
            vis[2] = 1;
    }
    else if (l == 3)
    {
        if (vis[3])
        {
            vis[1] = vis[2] = 1;
        }
        else
        {
            vis[3] = 1;
        }
    }
    else if (l == 4)
    {
        if (vis[4] == 1)
        {
            vis[1] = 1;
            vis[3] = 1;
        }
        else
        {
            vis[4] = 1;
        }
    }

    if (r == 1)
    {
        if (vis[1])
            ans++;
    }
    else if (r == 2)
    {
        if (vis[2])
        {
            if (vis[1])
                ans += 2;
            else
                ans++;
        }
    }
    else if (r == 3)
    {
        if (vis[3])
        {
            if (vis[2])
            {
                if (vis[1])
                {
                    ans += 3;
                }
                else
                    ans += 2;
            }
            else
            {
                if (vis[1])
                {
                    ans += 1;
                }
            }
        }
    }
    else if (r == 4)
    {
        if (vis[4] == 1)
        {
            if (vis[3])
            {
                if (vis[2])
                {
                    if (vis[1])
                        ans += 4;
                    else
                        ans += 3;
                }
                else
                {
                    if (vis[1])
                        ans += 2;
                    else
                        ans++;
                }
            }
            else
            {
                if (vis[1])
                    ans++;
            }
        }
    }
    cout << ans << endl;
}

I. Italian Calzone & Pasta Corner

找一个最大上升子序列 路径里 图很小 对每个点跑bfs 注意剪枝

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
int mp[300][300];
int vis[300][300],f[300][300];
int fx[4][2]={1,0,-1,0,0,1,0,-1};
void solve(){
	int n,m;cin>>n>>m;
	 for(int i=1;i<=n;i++){
	 	for(int j=1;j<=m;j++) cin>>mp[i][j];
	 }
	 int ans=0;
	 for(int i=1;i<=n;i++){
	 	for(int j=1;j<=m;j++){
	 		int res=0;
	 		if(vis[i][j]) continue;
	 		for(int x=1;x<=n;x++){
	 			for(int y=1;y<=m;y++) f[x][y]=0;
			 }
			 queue<array<int,2>> que;
			 que.push({i,j});
			 f[i][j]=1;
			 vis[i][j]=1;
			 res=1;
			 while(que.size()){
			 	int x=que.front()[0],y=que.front()[1];
			 	que.pop();
			 	for(int v=0;v<4;v++){
			 		int xx=x+fx[v][0],yy=y+fx[v][1];
			 		if(xx<1||xx>n||yy<1||yy>m||f[xx][yy]||mp[x][y]>mp[xx][yy]) continue;
			 		f[xx][yy]=1;res++; 
			 		vis[xx][yy]=1;
			 		que.push({xx,yy});
				 }
			 	
			 }
			 ans=max(ans,res);
		 }
	 }
	 cout<<ans<<"\n";
}
signed main(){
    close;
	solve();
}

L. Lazy Printing

给打印机 找长度在限制范围内的最小的模板串数量

贪心地不停向后枚举 然后用hash优化下过了 但是这个还是n2的 数据太弱 标准做法kmp

#include <bits/stdc++.h>

#define close                         \
	std::ios::sync_with_stdio(false); \
	cin.tie(0);                       \
	cout.tie(0)
using namespace std;
typedef unsigned long long ULL;

const int N = 1007;
const int MANX = 4e5+7;
int n, d,P=131;
char s[200010];
const int inf = 2e9;
ULL h[MANX], p[MANX];
ULL get(int l, int r) {
	return h[r] - h[l - 1] * p[r - l + 1];
}
inline int find(int now, int i) {
//	int pos = now;
	int t = 0;
	int ans=now;
	int pos=now;
	pos+=i;
	ULL k=get(now,pos);
	while(pos<=n){
		ULL tmp=get(pos-i,pos);
		if(tmp!=k) break;
		ans=pos;
		pos+=i;
	}
	pos=now;
	while (s[pos] == s[ans]) {
		++pos;
		++ans;
		++t;
		if (t == i) {
			t = 0;
			pos = now;
		}
	}
	return ans;
}
int main() {
	close;
	p[0] = 1;
	cin >> s+1 >> d;
	n = strlen(s+1);
	for (int i = 1; i <= n; i ++ ) {
		h[i] = h[i - 1] * P + s[i];
		p[i] = p[i - 1] * P;
	}

	int now = 1;
	int ans = 0;
	while (now <= n) {
		int mx = 0;
		for (int i = 1; i <= d; ++i) {
			int k = find(now, i);
			if (k > mx) {
				mx = k;
			}
		}
		++ans;
		now = mx;
	}
	cout << ans;
}

M. Maze in Bolt

可以旋转的锁 一步一步转看看能不能下去 并且可以换头的方向

队友搓的搜索 很牛

#include <iostream>
#include <queue>
using namespace std;

const int N = 1007;
char mp[N][N];
int row, col;
int flag[N][N];
int vis[N][N];
char tag[N];
int bg = -1;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool check(int r, int c)
{
    for (int i = 0; i < col; i++)
    {
        if (tag[(bg + i) % col] == '0')
            continue;
        if (mp[r][(c + i) % col] == '1')
            return false;
    }
    return true;
}

bool bfs()
{
    for (int i = 1; i <= row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            if (check(i, j))
                flag[i][j] = 1;
            else
                flag[i][j] = 0;
            vis[i][j] = 0;
            // if (flag[i][j])
            //     cout << i << ' ' << j + 1 << endl;
        }
    }
    queue<pair<int, int>> q;
    bool getans = false;
    for (int i = 0; i < col; i++)
    {
        if (flag[1][i])
        {
            vis[1][i] = 1;
            q.push({1, i});
        }
    }
    while (q.size())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (x == row)
        {
            getans = true;
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = (y + dy[i] + col) % col;
            if (xx <= 0 || xx > row)
                continue;
            if (vis[xx][yy])
                continue;
            if (flag[xx][yy] == 0)
                continue;
            vis[xx][yy] = 1;
            q.push({xx, yy});
        }
    }
    return getans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> row >> col;
    for (int i = 0; i < col; i++)
    {
        cin >> tag[i];
        // cout << tag[i];
        if (tag[i] == '1' && bg == -1)
            bg = i;
    }
    // cout << endl;
    // cout << bg << endl;
    for (int i = 1; i <= row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            cin >> mp[i][j];
        }
    }
    if (bg == -1)
    {
        cout << "Y";
        return 0;
    }
    if (bfs())
        cout << "Y";
    else
    {
        for (int i = 0; i < col - i - 1; i++)
        {
            // cout << i << ' ' << col - i << endl;
            swap(tag[i], tag[col - i - 1]);
        }
        for (int i = 0; i < col; i++)
        {
            // cout << tag[i];
            if (tag[i] == '1')
            {
                bg = i;
                break;
            }
        }
        // cout << endl;
        if (bfs())
            cout << "Y";
        else
            cout << "N" << endl;
    }
}

A. Asking for Money

每个人被一个人要钱时候可以对两个人要钱

随机某个人被要1元 问谁最后有可能不亏钱

不亏钱条件是有一个点能同时到达三个点

建反图 三个点同时到达一个点 复杂度大大优化

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
vector<int> adj[MAXN];
pair<int,int> e[MAXN];
int vis[MAXN],tmp[MAXN];
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int u,v;cin>>u>>v;
		adj[u].push_back(i);
		adj[v].push_back(i);
		e[i]={u,v};
	}
	for(int i=1;i<=n;i++){
		for(int it=1;it<=n;it++) vis[it]=0,tmp[it]=0;
		queue<int>que;
		que.push(i);
		vis[i]=1;
		while(que.size()){
			int x=que.front();
			que.pop();
			for(auto &v:adj[x]){
				if(!vis[v]){
					vis[v]=1;
					que.push(v);
				}
			}
		}
		for(int j=1;j<=n;j++) if(vis[j]) tmp[j]++;
		//
		for(int it=1;it<=n;it++) vis[it]=0;
		que.push(e[i].first);
		vis[e[i].first]=1;
		while(que.size()){
			int x=que.front();
			que.pop();
			for(auto &v:adj[x]){
			    if(v==i) continue;
				if(!vis[v]){
					vis[v]=1;
					que.push(v);
				}
			}
		}
		for(int j=1;j<=n;j++) if(vis[j]) tmp[j]++;
		//
		for(int it=1;it<=n;it++) vis[it]=0;
		que.push(e[i].second);
		vis[e[i].second]=1;
		while(que.size()){
			int x=que.front();
			que.pop();
			for(auto &v:adj[x]){
			    if(v==i) continue;
				if(!vis[v]){
					vis[v]=1;
					que.push(v);
				}
			}
		}
		for(int j=1;j<=n;j++) if(vis[j]) tmp[j]++;
		int flag=0;
		for(int j=1;j<=n;j++){
			if(tmp[j]==3) flag=1;
		}
		if(flag) cout<<"Y";
		else cout<<"N";
	}
}
signed main(){
	solve();
}

C. City Folding

码力太弱 推不出公式

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int f[MAXN];
vector<int> ans;
void solve(){
	int n,p,h;cin>>n>>p>>h;
	p--;h--;
	for(int i=n-1;i>=0;i--){
		if(h>=(1LL<<i)) {
			f[n-i-1]=1;
			h=(1LL<<(i+1))-1-h;
		}
	//cout<<"# h = "<<h<<" "<<f[n-i-1]<<"\n";
	} 
	//预处理是否需要翻动来增加高度，f为1表示需要增加一次高度
	//3 8 3 第一次翻动增加4 不需要 第二次翻动增加2 需要，翻动后长度变为剩下的长度 
	for(int i=n-1;i>=0;i--){
		//第i次翻动 h改变的是1<<(n-i-1) p改变的是1<<i 
		if(!f[i]){ 
	//	cout<<f[i];//需要增加h 
			if(p<(1LL<<i)){
				cout<<"R"; 
			}
			else{
				cout<<"L";
				p-=(1LL<<i);
			}
		}
		else{//需要的长度大 
	//	cout<<f[i];
		//反转后高度会改变 
			if(p<(1LL<<i)){
				cout<<"L";
				p=(1LL<<i)-1-p; 
			}
			else{
				cout<<"R";
				p=(1LL<<(i+1))-1-p;
			}
		}
	} 
}
signed main(){
	solve();
}

The 2022 ICPC Asia Nanjing Regional Contest

赛时过题AGIM 补题D

A. Stop, Yesterday Please No More

有很多袋鼠 满的 然后会根据题目给的走 问有几种放洞的方法 可以让最后剩下k个袋鼠

我一开始在走洞 写了一个自己样例都过不去的做法

队友上机敲了一发走袋鼠的 直接过了

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <iomanip>
// 小数位    cout<<fixed<<setprecision(12)<<dis[n+1]<<endl;
using namespace std;
#define close                         \
    std::ios::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)

const int N = 1e3 + 7;
typedef long long ll;

int row, col, lv;
string s;
ll vis[N][N];

ll count(int x1, int y1, int x2, int y2)
{
    // cout << vis[x2][y2] << " " << vis[x1 - 1][y1 - 1] << ' ' << vis[x1 - 1][y2] << ' ' << vis[x2][y1 - 1] << endl;
    return vis[x2][y2] + vis[x1 - 1][y1 - 1] - vis[x1 - 1][y2] - vis[x2][y1 - 1];
}

void solve()
{
    cin >> row >> col >> lv;
    for (int i = 1; i <= row; i++)
        for (int j = 1; j <= col; j++)
            vis[i][j] = 0;
    cin >> s;
    ll v = 0, h = 0; // 竖直，水平
    ll mxv0, mxv1, mxh0, mxh1;
    mxv0 = mxv1 = mxh0 = mxh1 = 0;
    ll x = 1, y = 1;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'U')
        {
            v++;
            x = max(x, v + 1);
            mxv0 = max(mxv0, v);
        }
        else if (s[i] == 'D')
        {
            v--;
            mxv1 = min(mxv1, v);
        }
        else if (s[i] == 'L')
        {
            h--;
            y = max(y, -h + 1);
            mxh1 = min(mxh1, h);
        }
        else
        {
            h++;
            mxh0 = max(mxh0, h);
        }
    }

    ll szrow = row - mxv0 + mxv1, szcol = col - mxh0 + mxh1;
    if (szrow <= 0 || szcol <= 0)
    {
        if (lv == 0)
            cout << row * col << endl;
        else
            cout << 0 << endl;
        return;
    }

    // cout << szrow << ' ' << szcol << endl;
    // cout << x << ' ' << y << endl;
    vis[x][y] = 1;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'U')
        {
            x--;
        }
        else if (s[i] == 'D')
        {
            x++;
        }
        else if (s[i] == 'L')
        {
            y--;
        }
        else
        {
            y++;
        }
        vis[x][y] = 1;
    }
    for (int i = 1; i <= row; i++)
    {
        for (int j = 1; j <= col; j++)
        {
            vis[i][j] += -vis[i - 1][j - 1] + vis[i - 1][j] + vis[i][j - 1];
        }
    }
    // for (int i = 1; i <= row; i++)
    // {
    //     for (int j = 1; j <= col; j++)
    //     {
    // cout << vis[i][j] << ' ';
    // }
    // cout << endl;
    // }
    ll ans = 0;
    // cout << count(2, 2, 3, 3) << endl;
    ll sz = szrow * szcol;

    // for (int i = szrow; i <= row; i++)
    // {
    //     for (int j = szcol; j <= col; j++)
    //     {
    //         ll cnt = count(i - szrow + 1, j - szcol + 1, i, j);
    //         if (cnt + lv == sz)
    //             ans++;
    //     }
    // }
    // cout << ans << ' ';
    // ans = 0;
    for (int i = 1; i <= row; i++)
    {
        for (int j = 1; j <= col; j++)
        {
            ll cnt = count(max(1ll, i - szrow + 1), max(1ll, j - szcol + 1), i, j);
            if (cnt + lv == sz)
                ans++;
        }
    }
    cout << ans << endl;
}

int main()
{
    close;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

G. Inscryption

野兽合并 写太急了被我wa了一发

显然是合并越多越好 0可以变成1 所以是类似反悔贪心

0多了就把1个0变1

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
#define int ll
const ll MAXN =  1e6+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
int a[MAXN];
void solve(){
	int n;cin>>n;
	int cnt0=0,cnt1=0,cnt2=0;
	int now=0;
	int flag=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==0) cnt0++;
		else if(a[i]==1) cnt1++;
		else cnt2++;
		if(a[i]!=0)
		now+=a[i];
		else now-=1;
		if(now<0){
			if(cnt0){
				cnt0--;
				cnt1++;
				now+=2;
			}
			else flag=0;
		}
	}

	int fz=1+cnt1,fm=1+cnt1-cnt0-cnt2;
	if(!flag) cout<<"-1\n";
	else{
		int tmp=__gcd(fz,fm);
		cout<<fz/tmp<<" "<<fm/tmp<<"\n"; 
	}
}
signed main(){
	close; 
	int t;cin>>t;
	while(t--) 
	solve();
}

I. Perfect Palindrome

结论：全变成一样的

#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
//  #define int long long
using namespace std;
constexpr ll mod=1e9+7; 
const ll inf=0x3f3f3f3f;  
const ll INF=0x3f3f3f3f3f3f3f3f;  
const double eps=1e-10;  
const int N=2e5+10;
// struct node{
//     friend bool operator<(const node&a,const node&b){
//         return ;
//     }
// }
//priority_queue<ll,vector<ll>,greater<ll>>pq;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){char F[200];int tmp=x>0?x:-x;if(x<0) putchar('-');int cnt=0;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
inline int combination(int n,int k){int sum=0;if (n==k||k==0){return 1;}else{return combination(n-1,k)+combination(n-1,k-1);}}
map<char,int>mp;
void solve(){
    // int n=read();
    string s;
    mp.clear();
    cin>>s;
    for(int i=0;i<s.size();i++){
        mp[s[i]]++;
    }
    int maxx=-1;
    for(auto it:mp){
        int y=it.second;
        maxx=max(y,maxx);
    }
    cout<<s.size()-maxx<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    // int t=1;
   int t=read();
    while(t--){
        solve();
    }
}

M. Drain the Water Tank

队友写的 向量判上边和下边 因为给定顺序排过了 所以就看看是不是下凹和下平

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <iomanip>
// 小数位    cout<<fixed<<setprecision(12)<<dis[n+1]<<endl;
using namespace std;
#define close                         \
    std::ios::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)

const int N = 2e5 + 7;
const int inf = 2e9;

struct node
{
    int x, y;
} nd[N];

int n;

void solve()
{
    cin >> n;
    int mn = inf, index = 0;
    for (int i = 0; i < n; i++)
        cin >> nd[i].x >> nd[i].y;

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int x = nd[i].x, y = nd[i].y;
        int nx = (i + 1) % n;
        int xx = nd[nx].x, yy = nd[nx].y;
        int nxx = (nx + 1) % n;
        int xxx = nd[nxx].x, yyy = nd[nxx].y;

        if (x < xx && y > yy)
        {
            if (yyy > yy && (xxx >= xx || (yyy - yy) * (x - xx) < (y - yy) * (xxx - xx)))
                ans++;
        }
        else if (x == xx && y > yy)
        {
            if (yyy > yy && xxx > xx)
                ans++;
        }
        else if (x > xx && y > yy)
        {
            if (yyy > yy && xxx > xx && (yyy - yy) * (x - xx) < (y - yy) * (xxx - xx))
                ans++;
        }
    }
    // cout << ans << endl;
    for (int i = 0; i < n; i++)
    {
        int nx = (i + 1) % n;
        while (nd[i].y == nd[nx].y && nd[i].x < nd[nx].x)
            nx = (nx + 1) % n;
        if (nx == (i + 1) % n)
            continue;
        int pre = (n + i - 1) % n;
        if (nd[pre].y > nd[i].y && nd[(n + nx - 1) % n].y < nd[nx].y)
            ans++;
    }
    cout << ans << endl;
}

int main()
{
    close;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

D. Chat Program

一次可以加一个等差数列 问第k大的数最多是多大

二分答案 看看加上后>=mid的数是否大于k个

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define int ll
int n,k,m,c,d;
int a[MAXN],pre[MAXN];
bool check(int mid){
	int cnt=0;
	for(int i=1;i<=n;i++) pre[i]=0;
	for(int i=1;i<=n;i++){
		if(a[i]>=mid) cnt++;
		else{
			int tmp=mid-a[i];
			tmp-=c;
			int pos;
			if(tmp<=0) {
				pos=max(i-m+1,1LL);
				pre[pos]++;
				pre[i+1]--;
			}
			else{
				int p;
				if(d==0){
					continue;
				}
				p=tmp/d;
				if(p*d!=tmp) p++;
				if(p>m) continue;
				pos=i-p;
				if(pos<1) continue;
				p=max(i-m+1,1LL);
				pre[p]++;
				pre[min(pos+1,i+1)]--; 
			} 
		}
	}
	pre[1]+=cnt;
	for(int i=1;i<=n;i++){
		pre[i]=pre[i]+pre[i-1];
		if(pre[i]>=k) return true;
	}
	return false;
}
void solve(){
	cin>>n>>k>>m>>c>>d;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=0,r=INF;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	} 
	cout<<r;
}
signed main(){
	close;
	solve();
}

2019-2020 ICPC Asia Hong Kong Regional Contest

赛时过题BDG 补题EJ

B. Binary Tree

每次拿不改变奇偶性 算树的总大小就行了

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
void solve(){
	int n;cin>>n;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
	}
	if(n%2==1) cout<<"Alice\n";
	else cout<<"Bob\n";
}
signed main(){
	close;
	int t;cin>>t;
	while(t--)
	solve();
}

D. Defining Labels

类似进制转换 队友写的

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <iomanip> //fixed<<setprecision(12)<<
#include <utility> //pair模板
#include <cmath>
#include <random> //mt19937 mtrand(time(0));
#include <time.h>
#define close                         \
    std::ios::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 2;
const ll mod = 200907;
using namespace std;

int k, x;

void solve()
{
    //	freopen("data.in.txt","r",stdin);
    //	freopen("data.out.txt","w",stdout);
    cin >> k >> x;
    int d = 9 - (10 - k) + 1;
    // cout << d << endl;
    vector<int> ans;
    while (x > 0)
    {
        ans.push_back((x - 1) % d + (10 - k));
        // cout << (x - 1) % d + (10 - k);
        // x = (x - 1) / d + 1;
        x = (x / d) - (int)(x % d == 0);
    }
    for (int i = ans.size() - 1; i >= 0; i--)
        cout << ans[i];
    cout << endl;
}

int main()
{
    close;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

G. Game Design

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <iomanip> //fixed<<setprecision(12)<<
#include <utility> //pair模板
#include <cmath>
#include <random> //mt19937 mtrand(time(0));
#include <time.h>
#define close                         \
    std::ios::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 2;
const ll mod = 200907;
using namespace std;

int k, cnt;
map<int, int> wei, fa;

void dfs(int k, int f)
{
    cnt++;
    // cout << cnt << ' ' << f << endl;
    fa[cnt] = f;
    int tp = cnt;

    if (k == 1)
    {
        wei[tp] = 1;
        wei[f] += wei[tp];
        return;
    }
    k--;
    if (k % 2 == 0)
    {
        // cout << cnt << endl;
        dfs(2, tp);
        dfs(k / 2, tp);
    }
    else
    {
        dfs(k, cnt);
    }
    wei[f] += wei[tp];
}

void solve()
{
    //	freopen("data.in.txt","r",stdin);
    //	freopen("data.out.txt","w",stdout);
    cin >> k;
    if (k == 1)
    {
        cout << 2 << endl;
        cout << 1 << endl;
        cout << 1 << ' ' << 2 << endl;
        return;
    }
    // cout << k << endl;
    dfs(k, 0);
    cout << cnt << endl;
    for (int i = 2; i <= cnt; i++)
        cout << fa[i] << ' ';
    cout << endl;
    for (int i = 1; i <= cnt; i++)
        cout << wei[i] << ' ';
    cout << endl;
}

int main()
{
    close;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E. Erasing Number

能处于中位数的肯定能删

三个连续大数能变成两个的 对于每个数 数连续的大数n2去做

J. Junior Mathematician

数位dp 模板题 赛场看出来了不会写

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  1e4+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
ll dp[MAXN][62][62];//pos pre 贡献
// dp[i][j][m]
//轮流枚举每一位的情况 都可以由上一位推出 复杂度为O(10n)
//pre表示前缀和 来算此时数的大小
//第三维记录f[x]-x
//f[x] 增加了 pre*x,  x增加了x*1-^n
//贡献=贡献-x*10^n+pre*x
int p[MAXN],upper[MAXN],m;
void init(int x) {
	p[1]=1;
	for(int i=2; i<=x+1; i++) {
		p[i]=p[i-1]*10;
		p[i]%=m;
	}
}
ll dfs(int pos,int pre_num,int c,int flag) {
	int max_number;
	if(pos<=0) return c==0;
	if(!flag&&dp[pos][pre_num][c]!=-1) return dp[pos][pre_num][c];
	if(flag) max_number=upper[pos];
	else max_number=9;
	ll ret=0;
	for(int i=0; i<=max_number; i++) {
//转移方程

		ret+=dfs(pos-1,(i+pre_num)%m,((c-i*p[pos]+pre_num*i)%m+m)%m,flag&&(i==max_number));
		ret=(ret+mod)%mod;
	}
	ret=(ret+mod)%mod;
	if(!flag) dp[pos][pre_num][c]=ret;
	return ret;
}

void solve() {
	string a,b;
	cin>>a>>b>>m;
	int l=max(a.length(),b.length());
	init(l);
	int len=a.length();
	a[len-1]--;
	for(int i=0; i<=l+4; i++) {
		for(int j=0; j<=m; j++) {
			for(int x=0; x<=m; x++) {
				dp[i][j][x]=-1;
			}
		}
	}
	for(int i=len-1; i>=0; i--) {
		if(a[i]>='0'&&a[i]<='9') break;
		a[i]='9',a[i-1]--;
	}
	for(int i=0; i<len; i++) {
		upper[len-i]=a[i]-'0';
	}
	//cout<<"## "<<a<<"\n";
	ll aa=dfs(len,0,0,1);
	for(int i=0; i<=l+4; i++) {
		for(int j=0; j<=m; j++) {
			for(int x=0; x<=m; x++) {
				dp[i][j][x]=-1;
			}
		}
	}
	len=b.length();
	for(int i=0; i<len; i++) {
		upper[len-i]=b[i]-'0';
	}
	ll bb=dfs(len,0,0,1);
	cout<<(bb-aa+mod)%mod<<"\n";
}
signed main() {
	close;
	int t;cin>>t;
	while(t--) 
	solve();
}

The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)

赛时过题ACHM 补题EJ

A. Oops, It’s Yesterday Twice More

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <algorithm>
#include <iomanip> //fixed<<setprecision(12)<<
#include <utility> //pair模板
#include <cmath>
#include <random> //mt19937 mtrand(time(0));
#include <time.h>
#define close                         \
    std::ios::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 2;
const ll mod = 200907;
using namespace std;

int n, a, b;

void solve()
{
    //	freopen("data.in.txt","r",stdin);
    //	freopen("data.out.txt","w",stdout);
    cin >> n >> a >> b;
    if (a <= n / 2)
    {
        if (b <= n / 2)
        {
            for (int i = 1; i < n; i++)
                cout << "UL";
            for (int i = 1; i < b; i++)
                cout << 'R';
            for (int i = 1; i < a; i++)
                cout << 'D';
        }
        else
        {
            for (int i = 1; i < n; i++)
                cout << "UR";
            for (int i = 1; i < a; i++)
                cout << 'D';
            for (int i = 1; i <= n - b; i++)
                cout << 'L';
        }
    }
    else
    {
        if (b <= n / 2)
        {
            for (int i = 1; i < n; i++)
                cout << "DL";
            for (int i = 1; i < b; i++)
                cout << 'R';
            for (int i = 1; i <= n - a; i++)
                cout << 'U';
        }
        else
        {
            for (int i = 1; i < n; i++)
                cout << "DR";
            for (int i = 1; i <= n - a; i++)
                cout << 'U';
            for (int i = 1; i <= n - b; i++)
                cout << 'L';
        }
    }
}

int main()
{
    close;
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C. Klee in Solitary Confinement

对区间+k 找众数最多的情况

由于数的总数不多，因此考虑dp它+或者不+的状态 实时更新最大值

用map会t 于是对每个数+2e6变成数组

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  1e7+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
int mp[MAXN],tmp[MAXN],mx[MAXN]; 
int a[MAXN];
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=2e6; 
		mp[a[i]]++;
		tmp[a[i]+m]++;
		tmp[a[i]]--;
		if(tmp[a[i]]<0)
		tmp[a[i]]=0;
		mx[a[i]]=max(tmp[a[i]],mx[a[i]]);
		mx[a[i]+m]=max(tmp[a[i]+m],mx[a[i]+m]);
	} 
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,mp[a[i]]+mx[a[i]]);
	}
	cout<<ans;
}
signed main(){
	close;
	solve();
}

H. Crystalfly

树dp

在对u点进行dp的时候 有两种情况

第一种是所有v都删除 留个最大的 dp值由v的所有节点推出

第二种是留一个 但是这个节点的子节点贡献不保留 再由下面推出 然后再加上一个t=3的节点 然后再算v的子节点

取最大值就行 没写明白wa了好久

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  4e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int a[MAXN],b[MAXN];
vector<int> adj[MAXN];
int dp[MAXN],sum[MAXN];
void dfs(int u,int fa) {
	dp[u]=a[u];
	int tmp=0;
	int max_1=0;
	int max_2=0;
	for(auto v:adj[u]) {
		if(v==fa) continue;
		sum[u]+=a[v];
		dfs(v,u);
		tmp=max(tmp,a[v]);
		if(b[v]==3) {
			if(a[v]>a[max_1]) {
				max_2=max_1;
				max_1=v;
			} else if(a[v]>a[max_2]) {
				max_2=v;
			}
		}
		dp[u]+=dp[v];
		dp[u]-=a[v];
	}
	int temp=dp[u];
	for(auto &v:adj[u]){
		if(v==fa) continue;
		int k=a[v];
		for(auto &it:adj[v]){
			if(it==u) continue;
			k+=dp[it]-a[it];
		}
		if(v==max_1)
		dp[u]=max({temp+tmp,temp-dp[v]+a[v]+k+a[max_2],dp[u]});
		else dp[u]=max({temp+tmp,temp-dp[v]+a[v]+k+a[max_1],dp[u]});
	}
	dp[u]=max(dp[u],temp+tmp);
}
void solve() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i++) {
		cin>>b[i];
		if(b[i]==2) b[i]=1;
		adj[i].clear();
		dp[i]=0;
		sum[i]=0;
	}
	for(int i=1; i<n; i++) {
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	sum[0]=inf;
	dfs(1,0);
	cout<<dp[1]<<'\n';
}
signed main() {
	close;
	int t;
	cin>>t;
	while(t--)
		solve();
}

M. Windblume Festival

手玩一下发现结论 至少有一个改变符号 然后最多有n-1个改变符号 特判n=1的情况即可

改变符号贪心

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <algorithm>
#include <iomanip> //fixed<<setprecision(12)<<
#include <utility> //pair模板
#include <cmath>
#include <random> //mt19937 mtrand(time(0));
#include <time.h>
#define close                         \
    std::ios::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e6 + 7;
const ll mod = 200907;
using namespace std;

ll n, a[N], ans, sum;

void solve()
{
    //	freopen("data.in.txt","r",stdin);
    //	freopen("data.out.txt","w",stdout);
    cin >> n;
    ans = sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if (n == 1)
    {
        cout << a[1] << endl;
        return;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
            sum -= a[i];
        else if (i == n)
            sum += a[i];
        else
        {
            if (a[i] < 0)
                sum -= a[i];
            else
                sum += a[i];
        }
    }
    cout << sum << endl;
}

int main()
{
    close;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E. Paimon Segment Tree

历史和是一种线性的递推 可以由上一个递推过来 由此想到矩阵处理 因此用线段树维护矩阵 加val之后相当于乘矩阵 把求历史和过程中要用的全用矩阵维护好先

有点卡常 少取模！！尽量优化下矩阵 乘法只做一半之类的

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  5e4+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
const ll M = 4;
inline ll read() { //快读
	ll x=0,f=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		f|=(ch=='-');
		ch=getchar();
	}
	while(ch<='9'&&ch>='0') {
		x=(x<<1LL)+(x<<3LL)+
		  (ch^48);
		ch=getchar();
	}
	return f?-x:x;
}
struct matrix {
	ll x[M+1][M+1];
	matrix() {
		memset(x,0,sizeof(x));
	}
	ll* operator [] (int i) {
		return x[i];
	}
	matrix operator * (matrix b) const {
		matrix res;
		for(int i = 1; i <= M; i ++) {
			for(int j = 1; j <= M; j ++) {
				for(int k = i; k <= j; k ++) {
					res[i][j] += (( x[i][k] *b[k][j]) );
					res[i][j]%=mod;
				}
			}
		}
		return res;
	}
	matrix operator + ( matrix b) const {
		matrix res;
		for (int i = 1; i <=M; i ++) {
			for (int j = i; j <= M; j ++) {
				res[i][j] = (x[i][j] + b[i][j] );
				res[i][j]%=mod;
			}
		}
		return res;
	}
	bool operator != (matrix b) {
		for (int i = 1; i <= M; i ++) {
			for (int j = 1; j <=M; j ++) {
				if (x[i][j] != b[i][j])return true;
			}
		}
		return false;
	}
	void init() {
		for(int i = 1 ; i <=M ; i ++) {
			for(int j = i ; j <=M ; j ++) {
				x[i][j] = (i == j ? 1LL : 0LL);
			}
		}
	}
};
matrix mpow(matrix a,ll m) { //矩阵a的m次方
	matrix res;
	res.init();
	while(m>0) {
		if(m&1) res=res*a;
		a=a*a;
		m>>=1;
	}
	return res;
}
bool check(matrix a) {
	int flag=true;
	for(int i=1; i<=M; i++) {
		for(int j=1; j<=M; j++) {
			if(i!=j&&a.x[i][j]!=0) flag=false;
			else if(i==j&&a.x[i][j]!=1) flag=false;
		}
	}
	return flag;
}
struct Info {
	matrix sum;
};
Info operator +(const Info &a,const Info &b) {
	Info c;
	c.sum=a.sum+b.sum;
	return c;
}
matrix A;
ll a[MAXN];
struct node {
	matrix lazy;
	Info val;
} seg[MAXN<<2];
void up(int id) {
	seg[id].val=seg[id<<1].val+seg[id<<1|1].val;
}
void settag(int id,int l,int r,matrix tag) {
	matrix tmp;
	seg[id].val.sum=seg[id].val.sum*tag;
	seg[id].lazy=seg[id].lazy*tag;
}
void down(int id,int l,int r) {
	if(seg[id].lazy.x[3][4]==0) return;
	int mid=l+r>>1;
	settag(id<<1,l,mid,seg[id].lazy);
	settag(id<<1|1,mid+1,r,seg[id].lazy);
	seg[id].lazy.init();
}
void build(int id,int l,int r) {
	seg[id].lazy.init();
	if(l==r) {
		seg[id].val.sum[1][1]=1;
		seg[id].val.sum[1][2]=a[l];
		seg[id].val.sum[1][3]=a[l]*a[l]%mod;
		seg[id].val.sum[1][4]=a[l]*a[l]%mod;
		return;
	}
	int mid = l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void modify(int id,int l,int r,int ql,int qr,matrix val) {
	if (ql==l&&r==qr) {
		settag(id,l,r,val);
		return;
	}
	down(id,l,r);
	int mid =(l+r) >> 1;
	if (qr<=mid)
		modify(id <<1,l,mid,ql,qr,val);
	else if (ql>mid)
		modify(id<<1|1, mid+1,r,ql,qr,val);
	else {
		modify(id<<1,l,mid,ql,mid,val);
		modify(id<<1|1,mid+1,r,mid+1,qr,val);
	}
	up(id);
}
Info query(int id,int l ,int r,int ql,int qr) {
	if(ql==l&&r==qr) {
		return seg[id].val;
	}
	down(id,l,r);
	int mid=l+r>>1;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,mid)+query(id<<1|1,mid+1,r,mid+1,qr);
}
vector<array<int,3> > P;
vector<array<int,4> >  Q[MAXN];//id l r ty
ll ans[MAXN];
void solve() {
	int n,m,q;
//	cin>>n>>m>>q;
	n=read();
	m=read();
	q=read();
	for(int i=1; i<=n; i++) a[i]=read();
	build(1,1,n);
	P.push_back({0,0,0});
	for(int i=1; i<=m; i++) {
		int l,r,x;
//		cin>>l>>r>>x;
		l=read();
		r=read();
		x=read();
		P.push_back({l,r,x});
	}
	for(int i=1; i<=q; i++) {
		int l,r,x,y;
	//	cin>>l>>r>>x>>y;
		l=read();
		r=read();
		x=read();
		y=read();
		if(x!=0)
			Q[x-1].push_back({i,l,r,-1});
		Q[y].push_back({i,l,r,1});
	}
	for(auto it:Q[0]) {
		int id=it[0],l=it[1],r=it[2],ty=it[3];
		matrix tmp = query(1,1,n,l,r).sum;
		ans[id]+=ty*tmp[1][4];
	}
	for(int i=1; i<=m; i++) {
		int l=P[i][0],r=P[i][1],x=P[i][2];
		matrix tmp;
		tmp[1][1]=1;
		tmp[1][2]=x;
		tmp[1][3]=1LL*x*x%mod;
		tmp[1][4]=1LL*x*x%mod;
		tmp[2][2]=1;
		tmp[2][3]=2LL*x;
		tmp[2][4]=2LL*x;
		tmp[3][3]=1;
		tmp[3][4]=1;
		tmp[4][4]=1;
		modify(1,1,n,l,r,tmp);
		tmp.init();
		tmp[3][4]=1;
		if(l>1) {
			modify(1,1,n,1,l-1,tmp);
		}
		if(r<n) {
			modify(1,1,n,r+1,n,tmp);
		}
		for(auto it:Q[i]) {
			int id=it[0],l=it[1],r=it[2],ty=it[3];
			matrix tmp = query(1,1,n,l,r).sum;
			ans[id]+=ty*tmp[1][4];
		}
	}
	for(int i=1; i<=q; i++) {
		printf("%lld\n",(ans[i]%mod+mod)%mod);
	//	cout<<(ans[i]%mod+mod)%mod<<"\n";
	}
}
signed main() {
//	close;
	solve();
}

J. Xingqiu’s Joke

找因子用的很暴力 不会证明复杂度的办法

2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)

赛时过题EKL 补题AFHM

E. Evil Coordinate

重新排列路径 然后让路径不会经过某个点

顺时针方向绕着走好像就行了 赛时不小心 写挂了好久

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int fx[4][2]= {1,0,0,1,-1,0,0,-1}; //右 上 左 下
int f[4];
string str[4]= {"R","U","L","D"};
void solve() {
	int x,y;
	cin>>x>>y;
	string s;
	cin>>s;
	string ans;
	for(int i=0; i<4; i++) f[i]=0;
	for(auto ch :s) {
		if(ch=='R') f[0]++;
		else if(ch=='U') f[1]++;
		else if(ch=='L') f[2]++;
		else f[3]++;
	}
	int xx=f[0]-f[2];
	int yy=f[1]-f[3];
	if((xx==x&&yy==y)||(x==0&&y==0)) {
		cout<<"Impossible\n";
		return;
	}
	int px=0,py=0;
	int flag1=1,flag2=1,flag3=1,flag4=1;
	for(int i=0;i<4;i++){
		for(int j=1;j<=f[i];j++){
			px+=fx[i][0];
			py+=fx[i][1];
			if(px==x&&py==y) flag1=0;
		}
	}
	
	px=0;
	py=0;
	for(int i=0;i<4;i++){
		int p=(i+1)%4; 
		for(int j=1;j<=f[p];j++){
			px+=fx[p][0];
			py+=fx[p][1];
			if(px==x&&py==y) flag2=0;
		}
	}
	px=0;
	py=0;
	for(int i=0;i<4;i++){
		int p=(i+2)%4; 
		for(int j=1;j<=f[p];j++){
			px+=fx[p][0];
			py+=fx[p][1];
			if(px==x&&py==y) flag3=0;
		}
	}
    px=0;
	py=0;
	for(int i=0;i<4;i++){
		int p=(i+3)%4; 
		for(int j=1;j<=f[p];j++){
			px+=fx[p][0];
			py+=fx[p][1];
			if(px==x&&py==y) flag4=0;
		}
	}
    // cout<<flag1<<" "<<flag2<<" "<<flag3<<" "<<flag4<<'\n';
	if(flag1){
		for(int i=0;i<4;i++){
			for(int j=1;j<=f[i];j++){
				cout<<str[i]; 
			}
		}
	}
	else if(flag2){
		for(int i=0;i<4;i++){
			int p=(i+1)%4;
			for(int j=1;j<=f[p];j++){
				cout<<str[p]; 
			}
		}
	}
	else if(flag3){
		for(int i=0;i<4;i++){
			int p=(i+2)%4;
			for(int j=1;j<=f[p];j++){
				cout<<str[p]; 
			}
		}
	} 
	else if(flag4){
		for(int i=0;i<4;i++){
			int p=(i+3)%4;
			for(int j=1;j<=f[p];j++){
				cout<<str[p]; 
			}
		}
	}
	else{
		cout<<"Impossible";
	}
	cout<<'\n';
}
signed main() {
	int t;
	cin>>t;
	while(t--)
		solve();
}

K. K Co-prime Permutation

显然 当i位置上是i+1时 gcd必为1 否则为i时 gcd为i 推一下就行

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
void solve(){
	int n,k;cin>>n>>k;
	if(k==0){
		cout<<"-1";
	} 
	else{
		k--;
		for(int i=1;i<=k;i++){
			cout<<i+1<<" ";
		}
		cout<<"1 ";
		for(int i=k+2;i<=n;i++){
			cout<<i<<" ";
		}
	}
}
signed main(){
	close;
	solve();
}

L. Let’s Play Curling

没记错就是找两个蓝色石头中间最大红色数量

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <algorithm>
#include <iomanip> //fixed<<setprecision(12)<<
#include <utility> //pair模板
#include <cmath>
#include <random> //mt19937 mtrand(time(0));
#include <time.h>
#define close                         \
    std::ios::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int inf = 2e9;
const int N = 2e6 + 7;
const ll mod = 200907;
using namespace std;

int n, m;
vector<int> all, a, b;

void solve()
{
    //	freopen("data.in.txt","r",stdin);
    //	freopen("data.out.txt","w",stdout);
    cin >> n >> m;
    all.clear(), a.clear(), b.clear();
    for (int i = 1; i <= n; i++)
    {
        int tp;
        cin >> tp;
        // cout << tp << ' ';
        a.push_back(tp);
        all.push_back(tp);
    }
    // cout << endl;
    for (int i = 1; i <= m; i++)
    {
        int tp;
        cin >> tp;
        b.push_back(tp);
        all.push_back(tp);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    // for (int i = 0; i < all.size(); i++)
    // cout << all[i] << ' ';
    // cout << endl;
    for (int i = 0; i < a.size(); i++)
    {
        int tp = a[i];
        a[i] = lower_bound(all.begin(), all.end(), tp) - all.begin() + 1;
        // cout << a[i] << endl;
    }
    // cout << endl;
    for (int i = 0; i < b.size(); i++)
        b[i] = lower_bound(all.begin(), all.end(), b[i]) - all.begin() + 1;
    // cout << endl;
    int mx = 0;
    for (int i = 0; i < b.size() - 1; i++)
    {
        int l = upper_bound(a.begin(), a.end(), b[i]) - a.begin() + 1;
        int r = lower_bound(a.begin(), a.end(), b[i + 1]) - a.begin() + 1;
        // cout << l << ' ' << r << endl;
        mx = max(mx, r - l);
    }
    int l = upper_bound(a.begin(), a.end(), b[m - 1]) - a.begin() + 1;
    int r = lower_bound(a.begin(), a.end(), inf) - a.begin() + 1;
    mx = max(mx, r - l);
    l = 1;
    r = lower_bound(a.begin(), a.end(), b[0]) - a.begin() + 1;
    mx = max(mx, r - l);
    if (mx == 0)
        cout << "Impossible" << endl;
    else
        cout << mx << endl;
}

int main()
{
    close;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

A. Ah, It’s Yesterday Once More

额场上写差不多了 但是有一个孤立点没找到 寄了 就是斜着走

F. Fireworks

先推出期望计算公式 然后三分答案 场上三分太丑 挂了

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define double long double
double f(int x,int n,int m,double p){
	return ((double)x*n+m)/(1.0-(pow(1-p,x)));
}
void solve(){
	int n,m;
	double p;
	cin>>n>>m>>p;
	p/=10000.0;
	int l=0,r=inf;
	while(l<r){
		int mid1=l+(r-l)/3;
		int mid2=r-(r-l)/3;
		if(f(mid1,n,m,p)<f(mid2,n,m,p)) r=mid2-1;
		else l=mid1+1;
	}
	printf("%.8Lf\n",f(l,n,m,p));
}
signed main(){
	int t;cin>>t;
	while(t--)
	solve();
}

H. Harmonious Rectangle

小范围打表

M. Monster Hunter

感觉类似树上背包 枚举父亲贡献的节点与我与我邻居贡献的

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e3+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int dp[MAXN][MAXN][2],a[MAXN];// i为顶点的子树 已经用了j个 此时用/不用  减少的最大贡献
vector<int> adj[MAXN];
int n;
int ans=0;
int sum[MAXN];
int sz[MAXN];
void dfs_sum(int u,int fa) {
	sum[u]=a[u];
	sz[u]=1;
	for(auto &v:adj[u]) {
		sum[u]+=a[v];
		dfs_sum(v,u);
	}
	ans+=sum[u];
}
void dfs(int u,int fa) {
	dp[u][1][1]=sum[u];
	for(auto &v:adj[u]) {
		dfs(v,u);
		for(int i=sz[u]; i>=0; i--) { //枚举父节点删了几个 
			for(int j=sz[v];j>=0;j--){
				if(j>0)
				dp[u][j+i][0]=max(dp[u][j+i][0],dp[u][i][0]+max(dp[v][j][0],dp[v][j][1]+a[v]));
				else 
				dp[u][j+i][0]=max(dp[u][j+i][0],dp[u][i][0]+dp[v][j][0]);
				if(j>0&&i>0)
				dp[u][j+i][1]=max(dp[u][j+i][1],dp[u][i][1]+max(dp[v][j][0],dp[v][j][1]));
				else if(i>0)
				dp[u][j+i][1]=max(dp[u][j+i][1],dp[u][i][1]+dp[v][j][0]);
			}
		}
		sz[u]+=sz[v]; 
	}

//	cout<<"delet : u "<<u<<"\n";
//	for(int i=0;i<=n;i++) cout<<"i = "<<i<<" "<<dp[u][i][0]<<" "<<dp[u][i][1]<<"\n";
}
void solve() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		adj[i].clear();
		sum[i]=0;
		for(int j=0; j<=n; j++) dp[i][j][0]=dp[i][j][1]=0;
	}
	ans=0;
	for(int i=2; i<=n; i++) {
		int u;
		cin>>u;
		adj[u].push_back(i);
	}
	for(int i=1; i<=n; i++) cin>>a[i];
	dfs_sum(1,0);
	dfs(1,0);
	for(int i=0; i<=n; i++) {
		cout<<ans-max(dp[1][i][0],dp[1][i][1])<<" ";
	}
	cout<<"\n";
}
signed main() {
	int t;
	cin>>t;
	while(t--)
		solve();
}

2022 ICPC Southeastern Europe Regional Contest

赛时过题 AFGHN

A. AppendAppendAppend