2024-1-11 DAY2

D - Fixed Prefix Permutations

字典树开大一点

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

const int N = 1e6 + 10;
int n,m;
int a[N][11];
int tre[N][11]; 
int tot;

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) cin>>a[i][j];

		vector<int> pos(m+1);
		for(int j=1;j<=m;j++) pos[a[i][j]] = j;

		int p = 0;
		for(int j=1;j<=m;j++)
		{
			int c = pos[j];
			if(!tre[p][c]) tre[p][c] = ++tot;
			p = tre[p][c];
		}
	}

	for(int i=1;i<=n;i++)
	{
		int p=0;
	    int ans = m;
		for(int j=1;j<=m;j++)
		{
			int c=a[i][j];
			if(!tre[p][c])
			{
				//cout << "***" <<endl;
				ans = j-1;
				break;
			}
			p = tre[p][c];
		}
		cout << ans << " " ;
	}
	//cout<<tot;
	cout <<endl;
	for(int i=0;i<=tot;i++) memset(tre[i],0,sizeof tre[i]);
	tot = 0;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

1810D - Climbing the Tree

记得开LL

1810D - Climbing the Tree#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 10;

void solve(){
	int q;
	cin >> q;
	int l = -1 , r = -1;
	while(q--){
		int c;
		cin >> c;
		if(c==1){
			int a,b,n;
			cin >> a >> b >> n;
			int h1,h2;
			if(n>=2)
			{
				h1 = (a - b) * (n - 1) + a;
				h2 = (a - b) * (n - 2) + a + 1;
			}else
			if(n==1)
			{
				h2 = 1;
				h1 = a;
			}
			if(l==-1&&r==-1)
			{
				l = h2;
				r = h1;
				cout << 1 << " ";
			}
			else
			{
				if(h1<l||h2>r) cout << 0 << " ";
				else{
					l = max(l,h2);
					r = min(r,h1);
					cout << 1 << " ";
				}
			}
		}
		else
		{
			int a,b;
			cin >> a >> b;
			if(l==-1&&r==-1)
			{
				cout << -1 << " ";
				continue;
			}
			int t1,t2;
			if(l<=a)
			{
				t1 = 1;
			}
			else
			{
				t1 = (l-a)/(a-b) + 1;
				while((a-b)*(t1-1)+a<l) t1++;
			}

			if(r<=a)
			{
				t2 = 1;
			}
			else
			{
				t2 = (r-a)/(a-b) + 1;
				while((a-b)*(t2-1)+a<r) t2++;
			}
			// if(q==0)
			// {
			// 	cout <<endl;
			// 	cout << l << " " << r <<endl;
			// 	cout << t1 << " " << t2 <<endl;
			// 	cout <<endl;
			// }
			if(t1==t2)
			{
				cout << t1 << " ";
			}
			else
			{
				cout << -1 << " ";
			}
 		}	
	}
	cout << endl ;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

0对局匹配 - 蓝桥云课

顺手

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5 + 10;
int a[N],cnt[N];
int n,k;
int dp[N];

void solve(){
	cin >> n >> k;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
		cnt[a[i]] ++;
	}
	if(k==0)
	{
		int ans = 0;
		for(int i=0;i<N;i++)
			if(cnt[i]) ans++;
		cout << ans <<endl;
		return;
	}
	long long ans = 0;
	for(int i=0;i<k;i++)
	{
		dp[i]=cnt[i];
		dp[i+k]=max(cnt[i+k],cnt[i]);
		long long sum = 0;
		for(int j=i+k*2;j<N;j+=k)
		{
			dp[j]=max(dp[j-k],dp[j-2*k]+cnt[j]);
			sum = max(dp[j],sum);
		}
		ans += sum;
	}
	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}

F - L-shapes

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 110;

int n, m;
char board[N][N]; 
int vis[N][N]; //标记数组
int q[4][2]={{0,1},{1,0},{-1,0},{0,-1}};

bool check1(int x,int y){
	int cnt=0;
	bool ok = false;
	for(int i=x-1;i<=x+1;i++)
		for(int j=y-1;j<=y+1;j++)
			if(board[i][j]=='*')
			{
				cnt++;
				int cnt1=0;
				for(int k=0;k<4;k++)
				{
					int x1 = i+q[k][0];
					int y1 = j+q[k][1];
					if(x1>=x-1&&x1<=x+1&&y1>=y-1&&y1<=y+1&&board[x1][y1]=='*') cnt1++;
				}
				if(cnt1==2) ok=true;
			}
	return (cnt==3&&ok);
}

bool check2(int x,int y){
	int cnt=0;
	for(int i=x-1;i<=x+1;i++)
		for(int j=y-1;j<=y+1;j++)
			if(board[i][j]=='*')
			{
				cnt++;
			}
	return cnt==3;
}

void solve()
{
   memset(vis,0,sizeof vis);
   memset(board,0,sizeof board);
   cin >> n >> m;
   for(int i=1;i<=n;i++)
   	for(int j=1;j<=m;j++)
   		cin >> board[i][j];

   for(int i=1;i<=n;i++)
   	 for(int j=1;j<=m;j++)
   	 {
   	 	if(board[i][j]=='*'&&!vis[i][j])
   	 	if(!check1(i,j))
   	 	{
   	 		cout << "NO" <<endl;
   	 		return;
   	 	}
   	 }
   	 for(int i=1;i<=n;i++)
   	 	for(int j=1;j<=m;j++)
   	 	{
   	 		if(board[i][j]=='*')
   	 			if(!check2(i,j))
   	 			{
   	 				cout << "NO" <<endl;
   	 				return;
   	 			}
   	 	}

   	cout << "YES" <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}