LDU-五一假期專練（5.1）

J - Cunning Friends

博弈論：

題目大意：給出n個桶每個桶里面都有若干個小球，三個人做游戲，先手先進行操作，剩下的兩個人是一伙的，想讓先手輸掉，三個人輪流進行游戲，每個人選一個桶取出 > 0 個球，當一個人無法進行操作的時候，就輸掉了
后面的兩個人想讓先手輸掉，問先手能否贏得比賽

打表找規律：

typedef int itn;
int n, m;
int eq, da, xiao;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x = read;
		if (x > 2) da++;
		else if (x == 2) eq++;
		else xiao++;
	}
	if (da == 1) da--, eq++;
	if (da > 1) puts("Lose");
	else if (eq > 2) puts("Lose");
	else if (eq == 1) puts("Win");
	else {
		if (xiao % 3) puts("Win");
		else puts("Lose");
	}
	return 0;
}

/*
2 10
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
AB
ABBBBABBBB

10
*/

F - Binary Transformations

思維貪心
首先說一種錯誤的貪心策略：
先將所有的應該由1->0的部分進行轉換，然后將所有的0->1的部分進行轉換
在將1-> 0的程序中，按照權值從大到小進行處理；
在將0-> 1的程序中，按照權值從小到大進行處理；
這樣在某些情況下可能是最優的

但是 當有某一個位置兩位都是1，并且權值非常非常大的時候，我們首先可以先將這個數轉換為0，然后再進行上述操作，還有一點，如果這種情況有若干個位置都有，那么應該轉換那一部分 ？換一種說法就是我們應該轉換都少個才能滿足貪心上的最優呢？
因為在上面兩個位置都對應 1 的情況下，轉換為0也是有代價的！

這里給出思路來源，能夠很好的解決這種情況 博客鏈接
做法：如果不存在一個位置p (a[p]=1,b[p]=1)，那么答案就是貪心的先把所有的1，按價值從大到小變為0,所有的0,按價值從小到大變為1，如果存在一些位置p，我們就列舉一開始把多少p轉成0,顯然價值越大的p越優，現在考慮如何模擬，我們可以用2個set，一個維護一開始要從0變1的數，另一個維護最后要由1變0的數，插入O(log n)，遍歷O(n)，總的復雜度O(n²)

下面是個人的理解：
因為有兩位都是1的情況變換會對答案產生貢獻，所以說在考慮這里插入兩位都是1的情況
在前面就已經提到過，將1->0的程序中，要按照從大到小的順序進行，但是再用set維護的程序中，默認的順序是從小到大，所以就要采用一個逆向的迭代器；而將0->1的程序中是按照從小到大的順序來進行操作的，用迭代器遍歷就ok
因為考慮兩位值都是1的情況的時候，代價越大就可能會對答案產生較大的貢獻，在插入的程序中，所以要考慮從大到小的順序
然后維護一下操作的貢獻，記錄下最小值

typedef int itn;
int n;
ll a[maxn];
string s,t; 
ll sum = 0,ans = 0;
vector<ll> vet;
multiset<ll> st1,st2;
bool cmp(ll a,ll b){
	return a > b;
}
ll get(int x){
	ll ret = 0;
	ll s = sum;
	int pos = x;
	if(pos) st1.insert(vet[pos-1]),st2.insert(vet[pos-1]);
	multiset<ll> :: iterator it1;
	multiset<ll> :: reverse_iterator it2;
	/// 1-> 0  big -> small
	for(it2 = st1.rbegin();it2 != st1.rend();++it2){
		s -= *(it2);
		ret += s;
	}
	for(it1 = st2.begin();it1 != st2.end(); ++ it1){
		s += *(it1);
		ret += s;
	}
	return ret;
}
int main() {
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	cin >> s;
	cin >> t;
	s = "#" + s;
	t = "#" + t;
	for(int i=1;i<=n;i++){
		if(s[i] == '1') sum += a[i];
		if(s[i] != t[i]) {
			if(s[i] == '1') st1.insert(a[i]);
			else st2.insert(a[i]);
		}else if(s[i] == '1'){
			vet.push_back(a[i]);
		}
	}
	sort(vet.begin(),vet.end(),cmp);
	int siz = vet.size();
	ll ans = inf;
	// cout <<"ans :  " << ans <<endl;
	for(itn i=0;i<=siz;i++){
		ans = min(ans,get(i));
	}
	cout << ans <<endl;
	return 0;
}

A - Concerts

題面：

dp
首先這個題目的資料范圍是有點問題的，codeforces官方宣告了更改了之后的資料范圍：
Announcement
1 <= k <= 300 1 <= n <= 10^5
題意：
給出兩個由大寫字母組成的字符序列A,B，在B中找到序列A，還應滿足對應的兩個字符之間的距離（題目輸入）能夠滿足條件，求方案數
通過資料范圍來看應該是可以進行二維的dp,
我們使用dp[i][j] 表示狀態：A已經匹配i個位置，當前位置是在j ，當匹配成功的時候，可以發現
dp[i][j] == dp[i][j] + dp[i-1][j-val[i]-1]
匹配不成功的時候，可以發現
dp[i][j] == dp[i][j] + dp[i-1][j]

int n, m;
char a[maxn];
char b[maxn];
int val[30];
int dp[307][maxn];
int main() {
	// n < m -> n 300 m 1e5;
	cin >> n >> m;
	for (itn i = 1; i <= 26; i++) val[i] = read;
	cin >> a + 1;
	cin >> b + 1;
	for (int i = 1; i <= m; i++) { // len of b
		if (a[1] == b[i])
			dp[1][i] = 1;
	}
	for (itn i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i] == b[j]) {
				// 匹配成功
				int t = a[i - 1] - 'A' + 1; // 'A' == 64 + 1
				if (j - val[t] - 1 >= 1)
					dp[i][j] += dp[i - 1][j - val[t] - 1], dp[i][j] %= mod;
			}
			dp[i][j] += dp[i][j - 1];
			dp[i][j] %= mod;
		}
	}
	cout << dp[n][m] % mod << endl;
	return 0;
}

/*
2 10
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
AB
ABBBBABBBB

10
*/