传送门：Problem - G - Codeforces
题意：
思路：
注意：
n 的范围很小，大概率考察状态压缩
因此这个题可以考虑用 状压dp
f[i][j] 表示状态为 i 的选法，以第 j 首歌为结尾的播放列表中的歌曲总数
f[ i | 1 << k ][k] = max( f[ i | 1 << k ][k] , f[i][j] + 1 );
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 17;
int f[1 << N][N];
void solve()
{int n;map<string , int> mp;cin >> n;vector<int> a( n ) , b ( n );int cnt = 0;for( int i = 0 ; i < n; i++){string x , y; cin >> x >> y;if( !mp.count(x) ) mp[x] = ++cnt;if( !mp.count(y) ) mp[y] = ++cnt;a[i] = mp[x];b[i] = mp[y];}for( int i = 0 ; i < 1 << n; i++){for( int j = 0 ; j < n; j++){f[i][j] = -2e18;}}for( int i = 0 ; i < 1 << n; i++)for( int j = 0 ; j < n ;j++)if( i >> j & 1 ) f[i][j] = 1;// 初始化for( int i = 0 ; i < 1 << n; i++){for( int j = 0 ; j < n ;j++){if( i >> j & 1 ){for( int k = 0 ; k < n; k++){if( !(i >> k & 1) && ( a[j] == a[k] || b[j] == b[k] ) )f[i | 1ll << k ][k] = max( f[i | 1ll << k][k] , f[i][j] + 1 );}}}}int ans = 0;for( int i = 0 ; i < n ; i++){ans = max( ans , f[(1ll << n) - 1][i] );}cout << n - ans << endl;
}
signed main()
{int tt;cin >> tt;while(tt--)solve();return 0;
}传送门：Problem - B - Codeforces
题意：
思路：
转换 a[i-1] = a[i-1] - 1 ; a[i] = a[i] - 2 ; a[i+1] = a[i+1] - 1 等价为 a[i] = a[i] - 1 ; a[i+1] = a[i+1] - 2; a[i+2] = a[i+2] - 1;
操作a[i] 时 ， 会影响a[i + 1] , a[i + 2]的值，当a[ i + 1 ] < 0 或 a[i + 2] < 0 不符合题意
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n;cin >> n;vector<int> a( n + 1 );for( int i = 1; i <= n;i++) cin >> a[i];for( int i = 1; i <= n - 2 ; i++){if( a[i] < 0 ) {puts("NO"); return;}a[i + 1] -= 2 * a[i];a[i + 2] -= a[i]; a[i] = 0;}bool flag = true;for( int i = 1 ; i <= n; i++){if( a[i] )flag = false;}if( flag ){puts("YES");}else puts("NO");
}
signed main()
{int tt;cin >> tt;while(tt--)solve();return 0;
}传送门：Problem - C - Codeforces
题意：
思路：
如果遇到 map 时 去掉 'a' , pie 时 去掉 'i'
此时有个及其特殊的测试用例：mapie 这种情况需要特判（打比赛的时候就要小心这种特殊的测试用例，并且要会枚举）
AC代码：
#include<bits/stdc++.h>
using namespace std;
void solve()
{int n;cin >> n;string s;cin >> s;s = " " + s;int ans = 0;for( int i = 2 ; i <= n - 1; i++){if( s[i] == 'i'&& s[i-1] == 'p' && s[i + 1] == 'e' ){if( i >= 4 ) {if( s[i-2] == 'a' && s[i-3] == 'm' ) continue;}ans++;}else if( s[i] == 'a' && s[i - 1] == 'm' && s[i + 1] == 'p' )ans++ , i++;}cout << ans << endl;
}
signed main()
{int tt;cin >> tt;while(tt--)solve();return 0;
}传送门：Problem - C - Codeforces
题意：
思路：
假设 a > b
要求最小值 -> a ^ x 要变小 && b ^ x 要变大
若 a : 1101101
b : 1100011
若通过异或 使 a 减小 ， b 增大，并且操作后的 a < b，其实是重复的，无需改变第一位不同的
若改变第五位，a减小，b增大，并且操作后的 a > b，改变第五位 .......
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
void solve()
{int a , b , r;cin >> a >> b >> r;if( a < b ) swap(a , b);int ans = 0;int arr[62] , brr[62];// 一般long long 用62个即可for( int i = 0 ; i < 62 ; i++){if( a >> i & 1 ) arr[i] = 1;else arr[i] = 0;if( b >> i & 1 ) brr[i] = 1;else brr[i] = 0;}bool flag = true;for( int i = 61 ; i >= 0 ; i-- ){if( arr[i] != brr[i] ){if( flag ) flag = false;else {if( brr[i] == 0 ){int temp = 1ll << i;if( ans + temp <= r ) ans += temp;}}}}cout << (a - ans) - ( b + ans ) << endl;
}
signed main()
{int tt;cin >> tt;while(tt--)solve();return 0;
}传送门：Problem - G - Codeforces
思路：一个数组 ( n >= 2 ) 经过任意次 + - 操作，所得到的新数组可以由 gcd( a[1] , a[2] ... , a[n] )
表示
设 d = gcd( a[1] , a[2] ... a[n] )
解决此问题 肯定要使数组尽可能小，则就表示为 { 0 * d , 1 * d , 2 * d , ( n - 1 ) * d }
任意两个元素中间的值 为 d - 1 个数不存在，0 ，( n - 1 ) * d 中间不存在的元素一共有 ( n - 1 ) * ( d - 1 )，若 k > ( n - 1 ) * ( d - 1 ) 则答案大于 ( n - 1 ) * d ，也就是 ( n - 1 ) * d + ( k - ( n - 1 ) * ( d - 1 ) ) ，若k <= ( n - 1 ) * ( d - 1 ) ，则可以举一个测试得答案
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
void solve()
{int n, k;cin >> n >> k;vector<int> a(n + 1);int d = 0;for (int i = 1; i <= n; i++) cin >> a[i], d = gcd(d, a[i]);if (n == 1){if (k > a[1]) cout << k << endl;else cout << k - 1 << endl;return;}int t = (n - 1) * (d - 1);if (k > t){k -= t;cout << (n - 1) * d + k << endl;}else {if (k % (d - 1) == 0)cout << k / (d - 1) * d - 1 << endl;else cout << k / (d - 1) * d + k % (d - 1) << endl;}
}
signed main()
{int tt; cin >> tt;while (tt--)solve();return 0;
}
