2016 Multi-University Training Contest 2
A - Acperience
题意：给出w[]，求S((w[i]-aB[i])^2)的最小值(B[i]为1或-1)。
tags：一看到就搞了个三分上去，估计是精度问题，一直挖，23333。。
就是把这个公式推下去，最后化简为 ans=S(w[i]^2) - ((S(abs(w[i])))^2)/n 。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 100005;ll w[N], s1, s2, n; int main() {int T; scanf("%d", &T);while(T--){s1=s2=0;scanf("%lld", &n);rep(i,1,n) {scanf("%lld", &w[i]);s1+= w[i]*w[i], s2+= abs(w[i]); // 绝对值。。在这挖了几发 }s1=n*s1-s2*s2;printf("%lld/%lld\n", s1/__gcd(s1,n), n/__gcd(s1,n));}return 0; }
E - Eureka
题意： 给出 n个点，多个在同一条直线上的点可以构成一个集合，问有多少个集合。
tags：
I 水题
K 水题
L - La Vie en rose
题意：两个字符串A、B。 B可以通过交换相邻位置的字符(每次每个位置只能交换一下)生成其它多个字符串。问A的每个位置(a[i]到a[i+lenB-1])是否可以匹配B或由B生成的字符串。
tags： 好题 虽然题意有点迷，但确实好题，可以练练bitset压位。可以参考大佬博客
dp[i][j][k]表示A匹配到第 i个位置，B匹配到第 j个位置时的情况(k为0表示B第 j个位置不交换，为1表示第 j个位置和 j-1交换，为2表示和 j+1交换)。 然后dp转移：
dp[i][j][0] = (dp[i-1][j-1][0] or dp[i-1][j-1][1]) and (A[i]==B[j]) dp[i][j][1] = dp[i-1][j-1][2] and (A[i]==B[j-1]) dp[i][j][2] = (dp[i-1][j-1][0] or dp[i-1][j-1][1] ) and (A[i]==B[j+1])
直接写出循环就是：
for(int j=1; j<=lenB; ++j)for(int i=1; i<=lenA; ++i) {dp[i][j][k]= }
但这样O(N*M)肯定超时，这里就是关键，又一次体会到了二进制的神奇。把dp[][][]的第一位压入bitset，第二层for循环就可以利用bitset的位运算操作完成，实现常数优化，即O(N*M/w)卡过。 另外dp[][][]第二维因为每次只要用到上一次的数据，所以可以滚动数组优化内存。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 100005, M=5005;int la, lb; char A[N], B[N]; bitset<N> dp[2][3], bs[26]; int main() {int T; scanf("%d", &T);while(T--) {scanf("%d %d %s %s", &la, &lb, A+1, B+1);rep(i,0,25) bs[i].reset();rep(i,1,la) bs[A[i]-'a'][i]=1;int now=0, las;dp[0][0]=bs[B[1]-'a']; if(lb>1) dp[0][2]=bs[B[2]-'a'];rep(j,2,lb) {las=now, now^=1;dp[now][0] = ((dp[las][0] | dp[las][1])<<1) & bs[B[j]-'a']; // 因为求出的是第i-1位的，<<1转到第i位。&bs[]是检测A[]==B[]dp[now][1] = (dp[las][2]<<1) & bs[B[j-1]-'a'];if(j<lb) dp[now][2] = ((dp[las][0] | dp[las][1])<<1) & bs[B[j+1]-'a'];}rep(i,1,la) {int ii=i+lb-1;if(ii<=la && (dp[now][0][ii] || dp[now][1][ii])) putchar('1');else putchar('0');} puts("");}return 0; }
