| Solved | Pro.ID | Title | Ratio(Accepted / Submitted) |
| 1001 | fraction 辗转相除 | 4.17%(7/168) | |
| ok | 1002 | three arrays 字典树+贪心 | 12.69%(76/599) |
| 1003 | geometric problem | 1.59%(1/63) | |
 |
1004 | equation | 20.65%(310/1501) |
| |
1005 | permutation 1 | 24.77%(407/1643) |
| |
1006 | string matching | 23.12%(724/3131) |
| |
1007 | permutation 2 | 47.19%(688/1458) |
| ok | 1008 | line symmetric 计算几何 | 1.87%(11/588) |
| 1009 | discrete logarithm problem 离散对数 | 18.42%(7/38) | |
| 1010 | find hidden array 贪心 | 6.25%(2/32) |
1002 three arrays
题意
给定两个长度为1e5的数组$a_1,a_2,...a_n$、$b_1,b_2,...b_n$，重新排列，使得$a_i oplus b_i $的字典序最小。
$0 le a_i , b_i < 2^{30}$
思路
对a数组和b数组建立两个字典树，然后遍历n次这两个字典树，每次两个指针分别从两颗字典树移动，能同时向0走就走，能同时向1走就向1走，每次走到底层后就是一个答案。
// #pragma GCC optimize(2) // #pragma GCC optimize(3) // #pragma GCC optimize(4) #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> // #include<bits/extc++.h> // using namespace __gnu_pbds; using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /**********showtime************/ const int maxn = 1e5+9; int a[maxn],b[maxn]; int tot[2],rt[2]; int bz[33]; struct node{ int ch[2]; int fa; int sz; void init(int f) { ch[0] = ch[1] = 0; fa = f; sz = 0; } }tree[2][maxn * 30]; int shu[35]; void add(int p, int len, int flag) { if(len == 0){ tree[flag][p].sz++; return; } if(tree[flag][p].ch[shu[len]] == 0) { tree[flag][p].ch[shu[len]] = ++ tot[flag]; tree[flag][tot[flag]].init(p); } int nx = tree[flag][p].ch[shu[len]]; add(nx, len-1, flag); int lc = tree[flag][p].ch[0]; int rc = tree[flag][p].ch[1]; tree[flag][p].sz = tree[flag][lc].sz + tree[flag][rc].sz; } void insert(int val, int flag) { int len = 0; for(int i=0; i<=30; i++) shu[++len] = val % 2, val /= 2; add(rt[flag], 30, flag); } void display(int rt, int flag) { if(rt == 0) return ; // cout<<tree[flag][rt].sz<<endl; display(tree[flag][rt].ch[0], flag); display(tree[flag][rt].ch[1], flag); } vector<int>vec; void find(int a, int b, int cen, int val) { if(cen == 0) { vec.pb(val); tree[0][a].sz--; tree[1][b].sz--; return; } if(tree[0][ tree[0][a].ch[0] ].sz && tree[1][ tree[1][b].ch[0]].sz ) { find(tree[0][a].ch[0], tree[1][b].ch[0], cen-1, val); } else if(tree[0][ tree[0][a].ch[1] ].sz && tree[1][ tree[1][b].ch[1]].sz) { find(tree[0][a].ch[1], tree[1][b].ch[1], cen-1, val); } else if(tree[0][tree[0][a].ch[0]].sz && tree[1][ tree[1][b].ch[1]].sz){ find(tree[0][a].ch[0], tree[1][b].ch[1], cen-1, val + bz[cen-1]); } else { find(tree[0][a].ch[1], tree[1][b].ch[0], cen-1, val + bz[cen-1]); } tree[0][a].sz = tree[0][tree[0][a].ch[0]].sz + tree[0][tree[0][a].ch[1]].sz; tree[1][b].sz = tree[1][tree[1][b].ch[0]].sz + tree[1][tree[1][b].ch[1]].sz; } int main(){ int T; scanf("%d", &T); bz[0] = 1; for(int i=1; i<=30; i++) bz[i] = 2 * bz[i-1]; while(T--) { tot[0] = tot[1] = 0; rt[0] = ++tot[0]; tree[0][rt[0]].init(0); rt[1] = ++tot[1]; tree[1][rt[1]].init(0); int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &a[i]), insert(a[i], 0); for(int i=1; i<=n; i++) scanf("%d", &b[i]), insert(b[i], 1); vec.clear(); for(int i=1; i<=n; i++) { find(rt[0], rt[1], 30, 0); } sort(vec.begin(), vec.end()); for(int i=0; i<vec.size() - 1; i++) printf("%d ", vec[i]); printf("%d ", vec[vec.size() - 1]); // display(rt[0], 0); } return 0; }
1008 line symmetric
题意
给定一个多边形，定点最多有1000个，在最多移动一个点的情况下，此多边形是否能成为轴对称图形，变换后图形要保证是简单多边形。
思路
1）枚举相邻点，和间隔为2的两个点，令他们的中垂线为对称轴，判断是否可行。
2）注意点是，一个点如果在枚举的对称轴上，那么就是不可行的。
3）如果两个点如果在对称轴的两边，且要相互交换位子，那么这也是不可行的。
// #pragma GCC optimize(2) // #pragma GCC optimize(3) // #pragma GCC optimize(4) #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> // #include<bits/extc++.h> // using namespace __gnu_pbds; using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /**********showtime************/ const int maxn = 1e3+9; pii po[maxn]; int n; bool dc(int le, int ri, pii m, pii k){ // 判垂直 int a = (po[ri].se - po[le].se) * k.se; int b = (po[ri].fi - po[le].fi) * k.fi; if(a != -b) return false; // 判中点 pii mid; mid.fi = (po[le].fi + po[ri].fi) / 2; mid.se = (po[le].se + po[ri].se) / 2; if(k.fi == 0) { return mid.fi == m.fi; } a = mid.se * k.fi; b = k.se * mid.fi + m.se * k.fi - k.se * m.fi; return a == b; } bool gao(int p1, int p2, pii m, pii k) { if(k.fi == 0) { return (po[p1].fi - m.fi) * (po[p2].fi - m.fi) <= 0; } int tmp1 = po[p1].se * k.fi - k.se * po[p1].fi + m.se * k.fi- k.se * m.fi; int tmp2 = po[p2].se * k.fi - k.se * po[p2].fi + m.se * k.fi- k.se * m.fi; return 1ll*tmp1 * tmp2 <= 0; } bool check(int le, int ri) { int sl = le, sr = ri; pii m, k; m.fi = (po[le].fi + po[ri].fi) / 2; m.se = (po[le].se + po[ri].se) / 2; k.fi = po[ri].se - po[le].se; k.se = -1*(po[ri].fi - po[le].fi); int cnt = 0; for(int i=1; i <= (n+1) / 2; i++){ if(gao(sl, le, m, k) && gao(sr, ri, m, k) ) return false; if(dc(le, ri, m, k) == 0) cnt++; ri++; if(ri == n+1) ri = 1; le--; if(le == 0) le = n; } return cnt <= 1; } bool check1(int le, int ri, int mid) { int sl = le, sr = ri; pii m, k; m.fi = (po[le].fi + po[ri].fi) / 2; m.se = (po[le].se + po[ri].se) / 2; k.fi = po[ri].se - po[le].se; k.se = -1*(po[ri].fi - po[le].fi); // cout<<m.fi<<" , " << m.se<<endl; // cout<<k.fi<<" , " << k.se<<endl; int cnt = 0; for(int i=1; i <= n / 2; i++){ if(gao(sl, le, m, k) && gao(sr, ri, m, k)) return false; if(dc(le, ri, m, k) == 0) cnt++; ri++; if(ri == n+1) ri = 1; le--; if(le == 0) le = n; } if(dc(mid, mid, m, k) == 0) cnt++; return cnt <= 1; } int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%d%d", &po[i].fi, &po[i].se); po[i].fi *= 2; po[i].se *= 2; } if(n <= 4) { puts("Y"); continue; } int flag = 0; for(int i=1; i<=n; i++) { int nx = (i + 1) ; if(nx == n+1) nx = 1; int la = i - 1 ; if(!la) la = n; int mid = i; if(check1(la,nx, mid)) flag = 1; } for(int i=1; i<=n; i++) { int cur = i; int nx = i + 1; if(nx == n+1) nx = 1; if(check(cur, nx)) flag = 1; } if(flag) puts("Y"); else puts("N"); } return 0; } /* 5 -100 -100 0 0 -100 100 1 0 100 1 */