今天更废了。
\(30pts\ rk84\)。
今天的题
T1
机房大部分人都做出来了，可是我只是打了个暴力（还没拿分）。
这道题其实可以把 \((b_1,b_2,b_3,b_4)\) 分为 \((b_1,b_2),(b_3,b_4)\) 两个部分。
这样的话，我们就可以开一个桶，然后存 \(a_{b_1}\oplus a_{b_2}\)。
因为这个 \(b_1,b_2,b_3,b_4\) 是单调递增的，所以我们可以从左到右枚举一个中间点，统计后面的点，存左面的点，这样不会重复。
#include <iostream>using std::cin;
using std::cout;
const int N = (int)2e6 + 10;int a[N];
int cnt[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];long long ans = 0;for (int i = 1; i <= n; ++i){for (int j = i + 1; j <= n; ++j)ans += cnt[a[i] ^ a[j]];for (int j = 1; j <= i - 1; ++j)cnt[a[i] ^ a[j]]++;}cout << ans << '\n';return 0;
}
T2
死了，\(30pts\)。
假设某个数对应的是 \(0\)。
那么这个数很容易观察出来，因为这一行将都是 \(0\)。
然后考虑 \(p - 1\)。
那么 \([1,p - 1]\)，分别乘 \(p - 1\)，就会是 \((0,p - 1),(1, p - 2)\dots\)，他们的高位是互不相同的，且只有 \(p - 1\) 这样。
然后经过观察十进制的九九乘法表可以得到，如果第 \(i\) 行的高位有多少不同的数，那么 \(i\) 对应的数，就是这个数。
#include <iostream>
#include <cstring>using std::cin;
using std::cout;
const int N = 2010;int p;
int cnt;
int cn[N];
int re[N];
int ans[N];
int vis[N][N];
int a[N][N << 1];void read(int &x)
{x = 0;char c = getchar();int f = 1;while (!isdigit(c)){if (c == '-')f = -f;c - getchar();}while (isdigit(c)){x = x * 10 + c - '0';c = getchar();}x = x * f;
}int main()
{read(p);for (int i = 1; i <= p; ++i){for (int j = 1; j <= p; ++j){read(a[i][2 * j - 1]);read(a[i][2 * j]);cn[a[i][2 * j - 1]]++;cn[a[i][2 * j]]++;}}int max = cn[0];int idx = 0;for (int i = 0; i < p; ++i){if (cn[i] > max){idx = i;max = cn[i];}}ans[0] = idx;memset(cn, 0, sizeof(cn));for (int i = 1; i <= p; ++i){for (int j = 1; j <= p; ++j){if (!vis[i][a[i][2 * j - 1]]){cn[i]++;vis[i][a[i][2 * j - 1]] = true;}}if (cn[i] == 1){if (ans[0] != i - 1)ans[1] = i - 1;}elseans[cn[i]] = i - 1;}for (int i = 0; i <= p - 1; ++i)re[ans[i]] = i;for (int i = 0; i <= p - 1; ++i)cout << re[i] << ' ';cout << '\n';return 0;
}
T3
死了。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 200200
#define int long long
#define mod 1000000007
#define oo (1ll<<60)
#define getchar()(inBuf==lenBuf?lenBuf=(inBuf=Buf)+fread(Buf,1,1<<20,stdin):0,inBuf==lenBuf?EOF:*inBuf++)
char Buf[1<<20],*inBuf,*lenBuf;
IL int read()
{reg int x=0,f=0; reg 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 f?-x:x;
}IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL int Sub(reg int x,reg int y){return x<y?x-y+mod:x-y;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL void Dec(reg int &x,reg int y){x=Sub(x,y);}
IL int Mul(reg int x,reg int y){reg int r=x*y; return r<mod?r:r%mod;}int n,a[3][N],ans;
int dl[3][3][N],dr[3][3][N],d[3][3][N];IL bool cmin(reg int &x,reg int y){return x>y?x=y,1:0;}struct Node
{int x,y,w;IL bool operator <(const Node &a)const{return w>a.w;}
};const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int dis[3][N];void dijkstra(reg int p,reg int l,reg int r)
{for(reg int o=0,i,j;o<3;++o){for(i=0;i<3;++i)for(j=l;j<=r;++j)dis[i][j]=oo;dis[o][p]=a[o][p];for(j=l;j<=r;++j){if(j>l)for(i=3;i--;)cmin(dis[i][j],dis[i][j-1]+a[i][j]);for(i=1;i<3;++i)cmin(dis[i][j],dis[i-1][j]+a[i][j]);for(i=2;i--;)cmin(dis[i][j],dis[i+1][j]+a[i][j]);}for(j=r;j>=l;--j){if(j<r)for(i=3;i--;)cmin(dis[i][j],dis[i][j+1]+a[i][j]);for(i=1;i<3;++i)cmin(dis[i][j],dis[i-1][j]+a[i][j]);for(i=2;i--;)cmin(dis[i][j],dis[i+1][j]+a[i][j]);}for(j=l;j<=r;++j){if(j>l)for(i=3;i--;)cmin(dis[i][j],dis[i][j-1]+a[i][j]);for(i=1;i<3;++i)cmin(dis[i][j],dis[i-1][j]+a[i][j]);for(i=2;i--;)cmin(dis[i][j],dis[i+1][j]+a[i][j]);}for(i=0;i<3;++i)for(j=l;j<=r;++j)d[o][i][j]=dis[i][j];}
}int ys[N*6],len;struct Point
{int x,y,d;IL bool operator <(const Point &a)const{return x<a.x;}
}p[N*3],q[N*3];struct Bit
{int c[N*6];IL void clear(){std::fill(c+1,c+1+len,0);}IL int low(reg int x){return x&-x;}IL int ask(reg int x){reg int r=0; for(;x;x-=low(x))Pls(r,c[x]); return r;}IL void add(reg int x,reg int k){for(;x<=len;x+=low(x))Pls(c[x],k);}
}A,B;void cdq(reg int l,reg int r)
{if(l==r){for(reg int i=0,j;i<3;++i)for(j=0;j<i;++j)Pls(ans,dl[i][j][l]%mod);return;}reg int mid=l+r>>1;dijkstra(mid,l,r);for(reg int o=0,i,j,k;o<3;++o)for(k=0;k<3;++k)for(i=0;i<3;++i)for(j=l;j<=mid;++j){cmin(d[o][i][j],dl[k][i][j]+dl[k][o][mid]-a[k][l]);cmin(d[o][i][j],dr[k][i][j]+dr[k][o][mid]-a[k][r]);}for(reg int o=0,i,j;o<3;++o)for(i=0;i<3;++i)for(j=l;j<=mid;++j)dr[o][i][j]=d[o][i][j];dijkstra(mid+1,l,r);for(reg int o=0,i,j,k;o<3;++o)for(k=0;k<3;++k)for(i=0;i<3;++i)for(j=mid+1;j<=r;++j){cmin(d[o][i][j],dl[k][i][j]+dl[k][o][mid+1]-a[k][l]);cmin(d[o][i][j],dr[k][i][j]+dr[k][o][mid+1]-a[k][r]);}for(reg int o=0,i,j;o<3;++o)for(i=0;i<3;++i)for(j=mid+1;j<=r;++j)dl[o][i][j]=d[o][i][j];static int id[3][N];for(reg int u=0,v,o,i,j,x,cnt;u<3;++u){len=cnt=0;reg int ti=0,tj=0;for(o=0;o<3;++o)for(i=l;i<=mid;++i)id[o][i]=++ti,p[ti].d=dr[u][o][i]%mod;for(o=0;o<3;++o)for(i=mid+1;i<=r;++i)id[o][i]=++tj,q[tj].d=dl[u][o][i]%mod;for(v=0;v<3;++v)if(u!=v){++cnt;for(o=0;o<3;++o)for(i=l;i<=mid;++i){x=id[o][i];if(cnt==1)p[x].x=dr[v][o][i]-dr[u][o][i]-(u>v);else ys[++len]=p[x].y=dr[v][o][i]-dr[u][o][i]-(u>v);}for(o=0;o<3;++o)for(i=mid+1;i<=r;++i){x=id[o][i];if(cnt==1)q[x].x=dl[u][o][i]-dl[v][o][i];else ys[++len]=q[x].y=dl[u][o][i]-dl[v][o][i];}}std::sort(ys+1,ys+1+len),len=std::unique(ys+1,ys+1+len)-ys-1;for(i=1;i<=ti;++i)p[i].y=std::lower_bound(ys+1,ys+1+len,p[i].y)-ys;for(i=1;i<=tj;++i)q[i].y=std::lower_bound(ys+1,ys+1+len,q[i].y)-ys;std::sort(p+1,p+1+ti),std::sort(q+1,q+1+tj);A.clear(),B.clear();for(i=j=1;i<=ti;++i){while(j<=tj&&q[j].x<=p[i].x)A.add(q[j].y,1),B.add(q[j].y,q[j].d),++j;Pls(ans,Mul(A.ask(p[i].y),p[i].d)),Pls(ans,B.ask(p[i].y));}}cdq(l,mid),cdq(mid+1,r);
}main()
{n=read();for(reg int i=0,j;i<3;++i)for(j=1;j<=n;++j)a[i][j]=read();dijkstra(1,1,n);for(reg int o=0,i,j;o<3;++o)for(i=0;i<3;++i)for(j=1;j<=n;++j)dl[o][i][j]=d[o][i][j];dijkstra(n,1,n);for(reg int o=0,i,j;o<3;++o)for(i=0;i<3;++i)for(j=1;j<=n;++j)dr[o][i][j]=d[o][i][j]; cdq(1,n),printf("%lld\n",Mul(ans,2));
}
T4
死了。
假设我们只要求最大值。
#define WANT_LDEBUG
// #define LDEBUG_TO_ERR_TXT
// #define CALC_TIME
// #define CALC_MEM#ifdef CALC_MEM
bool m_be_;
#endif
#ifdef LOCAL
#include "D:/Code/C++/include/all.h"
#else
#include <bits/stdc++.h>
#define INCLUDED_ALL
#define ldebug(...) []() {}()
#define fast_io() \std::ios::sync_with_stdio(false); \std::cin.tie(nullptr)
#endif
using namespace std;
using i8 = signed char;
using i16 = short;
using i32 = int;
using i64 = long long;
using i128 = __int128;
using u8 = unsigned char;
using u16 = unsigned short;
using ui = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f64 = double;
using f96 = long double;
template <typename T, size_t F, size_t... Args> class mdarray {private:std::array<mdarray<T, Args...>, F> a;public:mdarray<T, Args...> &operator[](size_t i) { return a[i]; }const mdarray<T, Args...> &operator[](size_t i) const { return a[i]; }
};
template <typename T, size_t F> class mdarray<T, F> {private:std::array<T, F> a;public:T &operator[](size_t i) { return a[i]; }const T &operator[](size_t i) const { return a[i]; }
};
template <typename T, typename U> bool ckmax(T &a, const U &b) {return a < b && (a = b, true);
}
template <typename T, typename U> bool ckmin(T &a, const U &b) {return b < a && (a = b, true);
}
#ifdef CALC_TIME
auto t_be_ = std::chrono::high_resolution_clock::now();
#endif// ===== program begin ======constexpr u64 MOD = 1e9 + 7;
u64 adj(u64 a) { return a >= MOD ? a - MOD : a; }
void pls_eq(u64 &a, const u64 b) { a = adj(a + b); }
constexpr ui MAXN = 605, MAXK = 20;
ui N, K;
array<ui, MAXN> a;
struct Way {array<pair<int, u64>, MAXK> a;ui n;pair<int, u64> &operator[](size_t k) { return a[k]; }const pair<int, u64> &operator[](size_t k) const { return a[k]; }
};
array<array<array<array<Way, 2>, 2>, MAXN>, MAXN> dp;bool mode;
void merge_array(Way &a, const Way &b, int add, u64 mul) {if (a.n + b.n == 0 || mul == 0) {return;}static Way c;c.n = 0;ui pa = 0, pb = 0;while (pa < a.n && pb < b.n) {if (a[pa].first == b[pb].first + add) {c[c.n++] = make_pair(a[pa].first,adj(a[pa].second + b[pb].second * mul % MOD));++pa;++pb;} else if (a[pa].first > b[pb].first + add) {c[c.n++] = a[pa++];} else {c[c.n++] = make_pair(b[pb].first + add, b[pb].second * mul % MOD);++pb;}if (c.n == K) {break;}}while (pa < a.n && c.n < K) {c[c.n++] = a[pa++];}while (pb < b.n && c.n < K) {c[c.n++] = make_pair(b[pb].first + add, b[pb].second * mul % MOD);++pb;}// if (mode && find(c.a.begin(), c.a.begin() + c.n, make_pair(-1, 1ULL)) != c.a.begin() + c.n) {// ldebug("Here\n");// }a = c;
}
void test_case() {cin >> N >> K;for (ui i = 0; i < N; ++i) {cin >> a[i];}sort(a.begin(), a.begin() + N);dp[1][1][0][0][dp[1][1][0][0].n++] = make_pair(-a[0] * 2, 1);dp[1][1][0][1][dp[1][1][0][1].n++] = make_pair(-a[0], 1);dp[1][1][1][0][dp[1][1][1][0].n++] = make_pair(-a[0], 1);for (ui i = 1; i < N; ++i) {mode = (i == 3);for (ui j = 1; j <= i; ++j) {// for (ui k = 0; k < 2; ++k) {// for (ui l = 0; l < 2; ++l) {// ldebug("dp[{},{},{},{}]:{}", i, j, k, l, dp[i][j][k][l].n);// for (ui m = 0; m < dp[i][j][k][l].n; ++m) {// ldebug("<{},{}>", dp[i][j][k][l][m].first,// dp[i][j][k][l][m].second);// }// ldebug("\n");// }// }// 1. 新开一段// 1.1 头merge_array(dp[i + 1][j + 1][1][0], dp[i][j][0][0], -a[i], 1);merge_array(dp[i + 1][j + 1][1][1], dp[i][j][0][1], -a[i], 1);// 1.2 尾merge_array(dp[i + 1][j + 1][0][1], dp[i][j][0][0], -a[i], 1);merge_array(dp[i + 1][j + 1][1][1], dp[i][j][1][0], -a[i], 1);// 1.3 中间merge_array(dp[i + 1][j + 1][0][0], dp[i][j][0][0], -a[i] * 2,j + 1);merge_array(dp[i + 1][j + 1][0][1], dp[i][j][0][1], -a[i] * 2, j);merge_array(dp[i + 1][j + 1][1][0], dp[i][j][1][0], -a[i] * 2, j);if (j > 1) {merge_array(dp[i + 1][j + 1][1][1], dp[i][j][1][1], -a[i] * 2,j - 1);}// 2. 扩展连续段// 2.1 [0][0]merge_array(dp[i + 1][j][0][0], dp[i][j][0][0], 0, j * 2);merge_array(dp[i + 1][j][1][0], dp[i][j][0][0], a[i], 1);merge_array(dp[i + 1][j][0][1], dp[i][j][0][0], a[i], 1);// 2.2 [0][1]merge_array(dp[i + 1][j][0][1], dp[i][j][0][1], 0, j * 2 - 1);merge_array(dp[i + 1][j][1][1], dp[i][j][0][1], a[i], 1);// 2.3 [1][0]merge_array(dp[i + 1][j][1][0], dp[i][j][1][0], 0, j * 2 - 1);merge_array(dp[i + 1][j][1][1], dp[i][j][1][0], a[i], 1);// 2.4 [1][1]if (j > 1) {merge_array(dp[i + 1][j][1][1], dp[i][j][1][1], 0, j * 2 - 2);}if (j > 1) {// 3. 合并连续段merge_array(dp[i + 1][j - 1][0][0], dp[i][j][0][0], a[i] * 2,j - 1);merge_array(dp[i + 1][j - 1][0][1], dp[i][j][0][1], a[i] * 2,j - 1);merge_array(dp[i + 1][j - 1][1][0], dp[i][j][1][0], a[i] * 2,j - 1);merge_array(dp[i + 1][j - 1][1][1], dp[i][j][1][1], a[i] * 2,j - 1);}}}for (ui i = 0; i < K; ++i) {if (i >= dp[N][1][1][1].n) {cout << "-1 -1\n";} else {cout << dp[N][1][1][1][i].first << " " << dp[N][1][1][1][i].second<< "\n";}}
}// ===== program end =====#ifdef CALC_MEM
bool m_en_;
#endif
int main(int, char **) {fast_io();
#ifdef CALC_MEMcerr << llabs(&m_be_ - &m_en_) / 1048576.0 << "MB\n";
#endif// init();ui T = 1;// cin >> T;while (T--) {test_case();
#ifdef DEBUGcerr << endl;
#endif}
#ifdef CALC_TIMEauto t_en_ = std::chrono::high_resolution_clock::now();cerr << std::chrono::duration_cast<std::chrono::milliseconds>(t_en_ - t_be_).count()<< "ms\n"
#endifreturn 0;
}