以下为题解
/T1.决斗
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],l=1;
signed main() {
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) {
if(a[l]>=a[i]) continue ;//减不掉
l++;
}
cout<<n-l+1;
return 0;
}
//T2.超速检测
#include <bits/stdc++.h>
using namespace std;
#define double long double
int a[100005], d[100005], v[100005], p[100005];
int del[100005];
struct node {
int ql, qr;
friend bool operator<(node l, node r) {
if (l.ql != r.ql)
return l.ql < r.ql;
return l.qr > r.qr;
}
} s[100005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, m, L, V;
cin >> n >> m >> L >> V;
for (int i = 1; i <= n; i++)
cin >> d[i] >> v[i] >> a[i];
for (int i = 1; i <= m; i++)
cin >> p[i];
int tot = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= 0 && v[i] <= V)
continue;
if (a[i] > 0) {
int wei = V * V - v[i] * v[i];
wei /= (2 * a[i]);
wei += d[i];
if (v[i] > V)
wei = d[i] - 1;
int l = 1, r = m, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (p[mid] > wei) {
r = mid - 1;
ans = mid;
} else
l = mid + 1;
}
if (!ans)
continue;
s[++tot].ql = ans, s[tot].qr = m;
} else {
int l = 1, r = m, pos = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (p[mid] >= d[i]) {
r = mid - 1;
pos = mid;
} else
l = mid + 1;
}
if (!pos)
continue;
l = pos, r = m;
int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
double su = sqrt(v[i] * v[i] * 1.0 + 2.0 * a[i] * (p[mid] - d[i]));
if (su > V) {
l = mid + 1;
ans = mid;
} else
r = mid - 1;
}
if (ans < pos)
continue;
s[++tot].ql = pos, s[tot].qr = ans;
}
}
sort(s + 1, s + tot + 1);
int mr = 1000000000;
for (int i = tot; i >= 1; i--) {
if (mr <= s[i].qr)
del[i] = 1;
mr = min(mr, s[i].qr);
}
int ans = 0, fu = 0;
for (int i = 1; i <= tot; i++) {
// cout << s[i].ql << " " << s[i].qr << " " << del[i] << endl;
if (del[i]) {
del[i] = 0;
continue;
}
if (fu < s[i].ql) {
ans++;
fu = s[i].qr;
}
}
cout << tot << " " << m - ans << "\n";
}
}
//T3.染色
#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
typedef long long ll;
const int N=2e5+5,V=1e6+5;
int T,n,a[N];ll r[V];
inline void Solve(){
memset(r,-0x3f,sizeof r);
ll mxr=0,tgr=0;rd(n);
for(int i=1;i<=n;i++){
rd(a[i]);
ll tmpr=max(mxr,r[a[i]]+a[i])+tgr;
if(a[i]==a[i-1])tgr+=a[i];
r[a[i-1]]=max(r[a[i-1]],tmpr-tgr);
mxr=max(mxr,r[a[i-1]]);
}
mxr=0;
for(int i=1;i<=1000000;i++)mxr=max(mxr,r[i]);
printf("%lld\n",mxr+tgr);
}
signed main(){
rd(T);
while(T--)Solve();
return 0;
}
//T4.擂台游戏
#include <bits/stdc++.h>
using LL = long long;
const int N = 1 << 18 | 7;
const int M = 18;
int n, m, t, aa[N], a[N], c[N];
int b[N], r[N], id[N], lp[N], rp[N];
LL sum[N], ans[N];
char s[M][N];
void build() {
for(int i = 0; i < t; ++i) {
r[i + t] = 0;
id[i + t] = i;
b[i + t] = i + 1;
sum[i + t] = lp[i + t] = rp[i + t] = i + 1;
}
for(int i = t - 1; i >= 1; --i) {
r[i] = r[i << 1] + 1;
id[i] = id[i << 1] >> 1;
lp[i] = lp[i << 1];
rp[i] = rp[i << 1 | 1];
sum[i] = sum[i << 1] + sum[i << 1 | 1];
if(s[r[i]][id[i]] == '0')
b[i] = a[b[i << 1]] >= r[i] ? b[i << 1] : b[i << 1 | 1];
else
b[i] = a[b[i << 1 | 1]] >= r[i] ? b[i << 1 | 1] : b[i << 1];
}
}
LL vt[N], st;
int rd;
void dfs(int i, LL ss, int zl) {
if(i >= t) {
ans[i - t] = st + ss + lp[i];
return ;
}
LL trd = rd, tst = st;
if(s[r[i]][id[i]] == '0') {
if(b[i] == b[i << 1]) {
LL v = a[b[i]] >= rd ? b[i] : a[b[i]] + 1 >= zl ? 0 : vt[a[b[i]] + 1];
std::fill(ans + lp[i << 1 | 1] - 1, ans + rp[i << 1 | 1], v + ss);
}
else {
vt[r[i]] = vt[r[i] + 1];
dfs(i << 1 | 1, ss, zl);
}
rd = trd, st = tst;
rd = std::max(rd, r[i]);
st += sum[i << 1 | 1];
vt[r[i]] = st;
dfs(i << 1, ss, zl);
}
else {
vt[r[i]] = 0;
st = 0;
dfs(i << 1, ss + sum[i << 1 | 1] + tst, r[i]);
st = tst, rd = trd;
if(a[b[i << 1]] >= rd) {
rd = std::max(rd, r[i]);
vt[r[i]] = b[i << 1];
st += b[i << 1];
dfs(i << 1 | 1, ss, zl);
}
else {
int tp = std::max(r[i], a[b[i << 1]]) + 1;
vt[r[i]] = tp >= zl ? 0 : vt[tp];
dfs(i << 1 | 1, ss, zl);
}
}
vt[r[i]] = 0;
rd = trd, st = tst;
}
void solve() {
build();
for(int i = 1; i < t; i <<= 1)
if(s[r[i]][id[i]] == '0')
if(b[i] == b[i << 1])
std::fill(ans + lp[i << 1 | 1] - 1, ans + rp[i << 1 | 1], b[i]);
else {
vt[r[i]] = 0;
rd = st = 0;
dfs(i << 1 | 1, 0, 20);
}
else {
rd = r[i];
st = vt[r[i]] = b[i << 1];
dfs(i << 1 | 1, 0, 20);
}
LL val = 0;
for(int i = 1, x; i <= m; ++i) {
for(x = 0; (1 << x) < c[i]; ++x) ;
LL v = (1 << x) == c[i] ? b[t / c[i]] : ans[c[i]];
//printf("%lld ", v);
val ^= i * v;
}
printf("%lld\n", val);
}
int main() {
freopen("arena.in", "r", stdin);
freopen("arena.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &aa[i]);
for(int i = 1; i <= m; ++i)
scanf("%d", &c[i]);
for(t = n; t & (t - 1); t += t & -t) ;
for(int i = 1; (1 << i) <= t; ++i)
scanf("%s", s[i]);
int cases;
scanf("%d", &cases);
while(cases--) {
int x[4];
scanf("%d%d%d%d", &x[0], &x[1], &x[2], &x[3]);
for(int i = 1; i <= n; ++i)
a[i] = aa[i] ^ x[i & 3];
solve();
}
return 0;
}