idy的题又回来了，今天的题代码难度不大，考思维
题解：
第一题：贪心，%4找规律
#include<bits/stdc++.h> using namespace std; #define ll long long int is[22] = {-1, -1, -1, -1, 1, -1, 1, -1, 2, 1, 2, -1, 3, 2, 3}; int main(){ freopen("split.in","r",stdin); freopen("split.out","w",stdout); int q; scanf("%d", &q); while(q--){ ll x; scanf("%I64d", &x); if(x < 15) printf("%d ", is[x]); else { if(x % 4 == 0)printf("%I64d ", x/4); else if(x % 4 == 1 || x % 4 == 3)printf("%I64d ", x/4 - 1); else printf("%I64d ", x/4); } } }
第二题：
理解：其实这道题就是找边的集合有多少个；对于相互独立的点（x，y没有和别的一样的），我们可以用乘法原理，所以我们的任务就是求联通块的贡献；
我们考虑联通块的意义，就是我们建图的原理：这里面的一个点代表原图中的一条边，（x=3, y=4), 而里面的一条边代表原来的一个点例如（x=3, y=4)这两个点相连的边代表的就是(3, 4);
如果是一棵树，我们把根节点去掉，每个点（就是原图中的一条边）对应唯一一条边（相当于被原图中的一个点选中），所以这棵树除了全集我们都可以构造，每条边有选或不选，就是2^点数 - 1；
如果不是树，每个点（原图中的边）都可以找到一条边，就是2^点数；
问题又来了，建边复杂度是O(n^2)的，怎么办了；
我们把一个联通块并到一个并查集中，对于一个点可以建的边，只能对一个并查集贡献，我们就只放在一个并查集中好了；
注意原图和新图中的边是相互转换的，所以最后统计大小时是 点数 + 1 == 边数-->树
#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9 + 7; const int M = 1e5 + 8; struct Point {ll x, y; int id;}p[M]; bool cmp(Point a, Point b){return a.x < b.x;} bool cmp2(Point a, Point b){return a.y < b.y;} ll disx[M], disy[M]; int fa[M], siz[M], tot[M], n, totx, toty; bool vis1[M], vis2[M]; ll ksm(ll a, ll b){ ll ret = 1; for(; b; b >>= 1, a = a * a % mod) if(b & 1)ret = ret * a % mod; return ret; } int find(int x){ if(x == fa[x])return x; return fa[x] = find(fa[x]); } void uni(int x, int y){ int u = find(x), v = find(y); fa[u] = v; } int main(){ freopen("cross.in","r",stdin); freopen("cross.out","w",stdout); ll ans = 1; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%I64d%I64d", &p[i].x, &p[i].y), disx[i] = p[i].x, disy[i] = p[i].y, p[i].id = i; sort(disx + 1, disx + 1 + n); totx = unique(disx + 1, disx + 1 + n) - disx - 1; sort(disy + 1, disy + 1 + n); toty = unique(disy + 1, disy + 1 + n) - disy - 1; for(int i = 1; i <= n; i++){ p[i].x = lower_bound(disx + 1, disx + 1 + totx, p[i].x) - disx, p[i].y = lower_bound(disy + 1, disy + 1 + toty, p[i].y) - disy; fa[i] = i; } sort(p + 1, p + 1 + n, cmp); for(int i = 1; i < n; i++) if(p[i].x == p[i + 1].x){ uni(p[i].id, p[i + 1].id); } sort(p + 1, p + 1 + n, cmp2); for(int i = 1; i < n; i++) if(p[i].y == p[i + 1].y){ uni(p[i].id, p[i + 1].id); } for(int i = 1; i <= n; i++){ int h = p[i].x; int u = find(p[i].id); tot[u]++; if(!vis1[h]){ siz[u]++; vis1[h] = 1; } h = p[i].y; if(!vis2[h]){ siz[u]++; vis2[h] = 1; } // printf("%I64d %I64d %d %d ",p[i].x, p[i].y,p[i].id, u); } for(int i = 1; i <= n; i++) if(p[i].id == find(p[i].id)){ if(tot[p[i].id] == 1) ans = ans * 3 % mod; else if(siz[p[i].id] == tot[p[i].id] + 1) ans = ans * ( ksm(2, siz[p[i].id]) - 1) % mod; else ans = ans * ksm(2, siz[p[i].id]) % mod; } printf("%I64d ", ans); }
第三题：
dp[i][j] 表示第i个串是否包括j这个字串，他要不然是a或b中本来有的，要不然就是中间新出来的可以拿来更新；
而这个新的串只有两段长度为k会对后面的合并有贡献，所以中间我们不用存，空间就没有问题了；
时间复杂度O(2*n* 2^12); STL大法强
#include<bits/stdc++.h> using namespace std; const int L = 11, MAXN = (1 << (L + 1) ) + 10; int idc, son[205][2]; bool dp[205][MAXN]; string str[205], sta[MAXN]; void init(){ for(int i = 1; i <= L; i++) for(int s = 0; s < (1 << i); s++){ string &sc = sta[++idc]; sc.resize(i); for(int j = 0; j < i; j++) sc[j] = (char) ('0' + ((s>>j) & 1)); //cout<<sta[idc]<<endl; } } string merge(string a, string b){ string c = a + b; if(a.size() + b.size() <= 2 * L)return c; return c.substr(0, L) + c.substr(c.size() - L, L); } int main(){ freopen("string.in","r",stdin); freopen("string.out","w",stdout); int n, m; int cc = clock(); init(); scanf("%d", &n); for(int i = 1; i <= n; i++)cin>>str[i]; scanf("%d", &m); for(int i = 1; i <= m; i++){ int a, b; scanf("%d%d", &a, &b); son[i + n][0] = a, son[i + n][1] = b; str[i + n] = merge(str[a], str[b]); } //for(int i = 1; i <= 20; i++)cout<<sta[i]<<endl; for(int i = 1; i <= n + m; i++){ if(i <= n){ int nowlen = str[i].size(); for(int j = 1; j <= idc; j++){ int len = sta[j].size(); for(int k = 0; k + len - 1 < nowlen; k++) if(str[i].substr(k, len) == sta[j]) dp[i][j] = 1; } } else { for(int j = 1; j <= idc; j++){ int a = son[i][0], b = son[i][1]; dp[i][j] |= dp[a][j] | dp[b][j]; int len = sta[j].size(); for(int l = 1; l < len; l++) if(l > str[a].size() || len - l > str[b].size())continue; else if(str[a].substr(str[a].size() - l, l) + str[b].substr(0, len - l) == sta[j]){ dp[i][j] = 1; break; } } } } for(int i = n + 1; i <= n + m; i++){ bool ok[L + 1]; memset(ok, true, sizeof(ok)); for(int j = 1; j <= idc; j++) if(!dp[i][j]) ok[sta[j].size()] = 0; for(int j = L; j >= 0; j--) if(ok[j]){ printf("%d ",j);break; } } int tt = clock(); return 0; }