Niuniu's ball guessing game (dynamic planning + prefix influence)

Topic linking

https://ac.nowcoder.com/acm/contest/19483/F

Topic

Ideas

We use one $f[i][j]$ It means the first one i No. of operations j A ball in a cup , Because we constantly exchange cups , So we will have a prefix effect , So every time we pass directly $r$ and $l-1$ Just make a mapping

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int dp[N][10];
int a[10];
int n,m;

int main()
{
    
	scanf("%d%d",&n,&m);
	int A,B;
	for(int i = 0;i < 10; ++i) dp[0][i] = i;
	for(int i = 1;i <= n; ++i) {
    
		scanf("%d%d",&A,&B);
		for(int j = 0;j < 10; ++j) {
    
			dp[i][j] = dp[i-1][j];
		}
		swap(dp[i][A],dp[i][B]);
	}
	while(m--) {
    
		scanf("%d%d",&A,&B);
		for(int i = 0;i < 10; ++i) {
    
			a[dp[A-1][i]] = i;
		}
		for(int i = 0;i < 10; ++i) {
    
			printf("%d%c",a[dp[B][i]],i==9?'\n':' ');
		}
	}
	
	
	
	return 0;
}