2020牛客国庆集训派对题解合集
2020-10-20 本文已影响0人
云中翻月
2020牛客国庆集训派对1
A
题意
给定一个长度为1e5的字符串，求从结尾开始的最长回文子串。
题解
逆序暴力枚举回文子串起点，用字符串Hash判断是否为回文子串。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int maxn=4e5+5;
const int INF=0x3f3f3f3f;
const ull p1=131ull;
int n;
int len;
char s[maxn];
ull p[maxn],h[maxn],rh[maxn];
ull getHash(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
ull getrHash(int l,int r){
int l1=len-r+1;
int r1=len-l+1;
return rh[r1]-rh[l1-1]*p[r1-l1+1];
}
void solve(){
len=strlen(s+1);
p[0]=1ull;
h[0]=0ull;
rep(i,1,len){
p[i]=p[i-1]*p1;
h[i]=h[i-1]*p1+(s[i]-'a'+1);
}
reverse(s+1,s+len+1);
rep(i,1,len) rh[i]=rh[i-1]*p1+(s[i]-'a'+1);
// rep(i,1,len){
// D(h[i]);D(rh[i]);E;
// }
int ans=0;
// rep(i,1,len/2+1){
// if(2*i<=len&&getHash(1,i)==getrHash(i+1,2*i)) ans=max(ans,2*i);
// if(2*i-1<=len&&getHash(1,i)==getrHash(i,2*i-1)) ans=max(ans,2*i-1);
// }
rrep(i,len,len/2-1){
if(2*i-len>=1&&getHash(i,len)==getrHash(2*i-len,i)) ans=max(ans,2*len-2*i+1);
if(2*i-len-1>=1&&getHash(i,len)==getrHash(2*i-len-1,i-1)) ans=max(ans,2*len-2*i+2);
}
cout<<len-ans;
}
int main() {
// ios::sync_with_stdio(false);
// freopen("A.in","r",stdin);
scanf("%d%s",&n,s+1);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
B
题意
给定一个长度为1e5的序列a，求
题解
考虑每个作为区间最值的贡献，则根据辗转相除法的时间复杂度，在
到
中与
的最大公约数至多有
个。
因此可以从左到右依次将每个作为区间的右端点，然后将其作为最大值的区间（这个区间可以用一个单调递减的单调栈维护）的最大值更新为
（这一步可以用线段树区间修改）。接下来，只要从
位置不断向前二分的找出每一段最大公约数相同的区间（静态维护区间最大公约数可以用ST实现），累计贡献即可。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const int maxlogn=20;
const int INF=0x3f3f3f3f;
const int mod=1000000007;
int n;
int a[maxn];
struct SegmentTree{
int l,r;
int v,tag;
}tr[maxn<<2];
template <typename T>
inline void read(T &x) {
x = 0; T f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
template <typename T>
inline void w(T x) { if (x > 9) w(x / 10); putchar(x % 10 + 48); }
template <typename T>
inline void write(T x, char c) { if(x < 0) putchar('-'), x = -x;w(x); putchar(c); }
inline void spread(int rt){
if(!tr[rt].tag) return;
tr[rt<<1].tag=tr[rt<<1|1].tag=tr[rt].tag;
tr[rt<<1].v=1ll*tr[rt].tag*(tr[rt<<1].r-tr[rt<<1].l+1)%mod;
tr[rt<<1|1].v=1ll*tr[rt].tag*(tr[rt<<1|1].r-tr[rt<<1|1].l+1)%mod;
tr[rt].tag=0;
}
inline void pushup(int rt){
tr[rt].v=(tr[rt<<1].v+tr[rt<<1|1].v)%mod;
}
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r;
if(l==r) return;
int mid=l+r>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
}
inline void update(int rt,int l,int r,int v){
if(tr[rt].l>=l&&tr[rt].r<=r) {tr[rt].v=1ll*v*(tr[rt].r-tr[rt].l+1)%mod;tr[rt].tag=v;return;}
spread(rt);
int mid=tr[rt].l+tr[rt].r>>1;
if(mid>=l) update(rt<<1,l,r,v);
if(mid<r) update(rt<<1|1,l,r,v);
pushup(rt);
}
inline int ask(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].v;
spread(rt);
int ans=0;
int mid=tr[rt].l+tr[rt].r>>1;
if(mid>=l) ans=(ans+ask(rt<<1,l,r))%mod;
if(mid<r) ans=(ans+ask(rt<<1|1,l,r))%mod;
return ans;
}
int lans[maxn],top,stk[maxn];
int lg[maxn],f[maxn][maxlogn];
inline int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
void init(){
top=0,lg[1]=0;
rep(i,2,n) lg[i]=lg[i>>1]+1;
int t=log2(n/2)+1;
rep(i,1,n) f[i][0]=a[i];
rep(j,1,t) rep(i,1,n-(1<<j)+1) f[i][j]=gcd(f[i][j-1],f[i+(1<<j-1)][j-1]);
rep(i,1,n){
while(top&&a[stk[top]]<a[i]) top--;
lans[i]=(!top?0:stk[top])+1;
stk[++top]=i;
}
}
inline int query(int l,int r){
int t=lg[r-l+1];
return gcd(f[l][t],f[r-(1<<t)+1][t]);
}
int ans=0;
inline void work(int x,int ups){
if(x<=0) return;
int l=1,r=x;
int stdd=query(x,ups);
while(l<r){
int mid=l+r>>1;
// if(query(mid,x)==stdd) r=mid;
if(query(mid,ups)==stdd) r=mid;
else l=mid+1;
}
ans=(ans+1ll*stdd*ask(1,l,x))%mod;
work(l-1,ups);
}
void solve(){
init();
build(1,1,n);
rep(i,1,n){
update(1,lans[i],i,a[i]);
work(i,i);
}
write(ans,'\n');
}
int main() {
// ios::sync_with_stdio(false);
// freopen("B.in","r",stdin);
read(n);
rep(i,1,n) read(a[i]);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
C
题意
给定一棵1e5个点的树，每次可以切出一条链并接到另一个节点上。求将其转化为链的最少次数。
题解
结论题，统计这棵无根树所有度数大于2的节点树即可。
时间复杂度。
代码如下
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6;
int a[maxn],n;
long long ans;
int main()
{
int x,y;
cin>>n;
for(int i=1;i<n;i++){
cin>>x>>y;
a[x]++;a[y]++;
}
for(int i=1;i<=n;i++){
if(a[i]>2){
ans+=a[i]-2;
}
}
cout<<ans;
return 0;
}
D
题意
在二维平面上有一条直线和1e5个点，求在这个直线上找到一个点做一个半径为R的圆，最多能覆盖多少个点。
题解
逆向考虑，以每个点做半径为R的圆，则每个点对应的圆，在直线上对应一段有向区间。于是题目转化为在直线上找到一个点，使得包含它的区间尽量多。
这个问题，可以将区间左右端点的贡献分别标记为1和-1，然后将所有区间端点排序后，扫描一遍累加贡献即可。
时间复杂度。
代码如下
#define method_2
#ifdef method_1
#endif
#ifdef method_2
/*
100% accepted
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
const int maxn=+5;
const int INF=0x3f3f3f3f;
using namespace std;
#define pii pair<double,long long>
long long n;
double R,A,B;
const int N = 2e6 + 100;
struct Node {
double x,y;
} a[N];
vector<pii> v;
bool pd(int i) {
double l = -B,r = A;
double clac = l * a[i].y - a[i].x * r;
return clac < 0;
}
int main() {
// freopen("D.in","r",stdin);
scanf("%lld%lf%lf%lf",&n,&R,&A,&B);
for(int i = 1; i <= n; i++) {
scanf("%lf%lf",&a[i].x,&a[i].y);
double X = a[i].x * a[i].x + a[i].y * a[i].y;
double Y = A * A + B * B;
double I = (B * a[i].x - A * a[i].y) * (B * a[i].x - A * a[i].y);
if(I - R * R * Y > 1e-8) continue;
double len1 = ((pd(i))?-1:1)*sqrt(X - I / Y) - ((R * R - I / Y)>1e-8 ? sqrt(R * R - I / Y) : 0.0);
double len2 = ((pd(i))?-1:1)*sqrt(X - I / Y) + ((R * R - I / Y)>1e-8 ? sqrt(R * R - I / Y) : 0.0);
v.push_back(pii(len1,-1));
v.push_back(pii(len2,1));
}
sort(v.begin(),v.end());
int ans = 0,last = 0;
rep0(i,0,v.size()) {
last -= v[i].second;
ans = max(ans,last);
}
cout << ans << endl;
return 0;
}
#endif
E
题意
给定，求
上所有数字的约数个数和。
题解
结论题，答案即为。该式可以使用整除分块优化。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+5;
const int INF=0x3f3f3f3f;
ll solve(ll n) {
ll ans=0ll;
for(ll l=1,r; l<=n; l=r+1) {
r=n/(n/l);
ans+=(r-l+1)*(n/l);
}
return ans;
}
int main() {
// ios::sync_with_stdio(false);
// freopen("E.in","r",stdin);
ll n,m;
cin>>n>>m;
cout<<solve(m)-solve(n-1);
return 0;
}
#endif
#ifdef method_2
#endif
#ifdef method_3
/*
*/
#endif
F
题意
给定1e5个数，从中找出K个，使得它们的按位与的结果最大。
题解
位运算的特点是每一位相互独立，于是可以考虑从最高位向最低位贪心。即每一位如果有不小于K个数字在这一位的值为1，那么这一位就可以为1。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const int maxlogn=32;
const int INF=0x3f3f3f3f;
int n,k,a[maxn];
vector<int>v,tmp;
void solve(){
int ans=0;
rrep(j,maxlogn-1,0){
int cnt=0;
tmp.clear();
rep0(i,0,v.size()) if(v[i]&(1<<j)) cnt++,tmp.push_back(v[i]);
if(cnt>=k){
ans+=(1<<j);
v.clear();
rep0(i,0,tmp.size()) v.push_back(tmp[i]);
}
}
printf("%d",ans);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("F.in","r",stdin);
scanf("%d%d",&n,&k);
rep(i,1,n) scanf("%d",&a[i]),v.push_back(a[i]);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
G
题意
给定100个长度和为100的禁止字符串，要求构造一个长度为1e5的字符串不包含禁止字符串，求构造方案数。
题解
将所有禁止字符串插入AC自动机，于是没有被AC自动机匹配到的字符串结尾都为合法转移。所有转移方式可以构成一个矩阵，则该矩阵的n次方，即为最终存储方案数的矩阵。求矩阵的n次方可采用矩阵快速幂优化。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5e5+5;
const int maxm=200+5;
const int INF=0x3f3f3f3f;
const int mod=1000000007;
int n,m;
int ch[maxn][26],vis[maxn],fail[maxn],size=0;
char S[maxn];
struct mat{
int s[maxm][maxm];
void clear(){memset(s,0,sizeof(s));}
mat operator*(const mat x)const{
mat z;z.clear();
rep(i,0,size) rep(j,0,size) rep(k,0,size) z.s[i][j]=(1ll*s[i][k]*x.s[k][j]%mod+z.s[i][j])%mod;
return z;
}
}ans,base;
queue<int>q;
void solve(){
rep0(i,0,26) if(ch[0][i]) q.push(ch[0][i]);
while(q.size()){
int x=q.front();q.pop();
rep0(i,0,26){
int y=ch[x][i];
if(y) fail[y]=ch[fail[x]][i],vis[y]|=vis[fail[y]],q.push(y);
else ch[x][i]=ch[fail[x]][i];
}
}
ans.clear();base.clear();
rep(i,0,size) ans.s[i][i]=1;
rep(i,0,size) rep0(j,0,26){
if(vis[i]||vis[ch[i][j]]) continue;
base.s[i][ch[i][j]]+=1;
// D(i);D(j);E;
}
for(;n;n>>=1,base=base*base) if(n&1) ans=ans*base;
rep(i,1,size) ans.s[0][i]=(ans.s[0][i]+ans.s[0][i-1])%mod;
printf("%d",ans.s[0][size]);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("G.in","r",stdin);
scanf("%d%d",&n,&m);
while(m--){
int len,u=0;
scanf("%d%s",&len,S);
rep0(i,0,len){
int c=S[i]-'a';
// D(c);E;
if(!ch[u][c]) ch[u][c]=++size;
u=ch[u][c];
}
vis[u]|=1;
}
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
const int N = 5e5 + 100,mod = 1e9 + 7;
int ch[N][26],vis[N],fail[N],n,m,size;
char S[N];
struct matrix {
int s[210][210];
void clear() {memset(s,0,sizeof(s));}
matrix operator *(const matrix x) const {
matrix z;z.clear();
for(int i = 0;i <= size;i++) {
for(int j = 0;j <= size;j++) {
for(int k = 0;k <= size;k++) {
z.s[i][j] = (z.s[i][j] + (1LL * s[i][k] * x.s[k][j] % mod)) % mod;
}
}
}
return z;
}
}ans,base;
int main() {
freopen("G.in","r",stdin);
scanf("%d%d",&n,&m);
while(m--) {
int len,u = 0;scanf("%d%s",&len,S+1);
for(int i = 1;i <= len;i++) {
int c = S[i] - 'a';
if(!ch[u][c]) ch[u][c] = ++size;
u = ch[u][c];
}vis[u] |= 1;
}
queue<int> Q;for(int i = 0;i < 26;i++) if(ch[0][i]) Q.push(ch[0][i]);
while(!Q.empty()) {
int u = Q.front();Q.pop();for(int i = 0;i < 26;i++) {
int v = ch[u][i];if(v) {
fail[v] = ch[fail[u]][i];vis[v] |= vis[fail[v]];Q.push(v);
}
else ch[u][i] = ch[fail[u]][i];
}
}
ans.clear();base.clear();
for(int i = 0;i <= size;i++) ans.s[i][i] = 1;
for(int i = 0;i <= size;i++) {
for(int j = 0;j < 26;j++) {
if(vis[i] || vis[ch[i][j]]) continue;
base.s[i][ch[i][j]] += 1;
D(i);D(j);E;
}
}
for(;n;n>>=1,base = base * base) if(n&1) ans = ans * base;
for(int i = 1;i <= size;i++) ans.s[0][i] = (ans.s[0][i] + ans.s[0][i-1]) % mod;
cout << ans.s[0][size] << endl;
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
H
题意
给定两个长度为1e5，且只含有ACTG四种字符的字符串。每次可以交换第一个字符串的两个字符，求将第一个字符串转化为第二个字符串的最小次数。
题解
因为字符只有四种，因此可以统计出四种字符的值。于是交换方式只有如下四种。
，不需要交换。
，需要一次交换。
，需要两次交换。
最后一种至多需要三次交换。
时间复杂度。
代码如下
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
using namespace std;
int maxn=1e6+7;
string a,b;
map<char,int>m;
int sum[4][4];
int main(){
cin>>a>>b;
int len=a.size();
m['A']=1;
m['G']=2;
m['T']=3;
m['C']=0;
int ans=0;
for(int i=0;i<len;i++){
if(m[a[i]]==m[b[i]]) continue;
sum[m[a[i]]][m[b[i]]]++;
}
int mn;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
mn=min(sum[i][j],sum[j][i]);
sum[i][j]-=mn;
sum[j][i]-=mn;
ans+=mn;
}
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
mn=min(sum[i][j],min(sum[j][k],sum[k][i]));
sum[i][j]-=mn;
sum[j][k]-=mn;
sum[k][i]-=mn;
ans+=mn*2;
}
}
}
for(int i=0;i<4;i++) ans+=sum[i][3]*3;
cout<<ans;
}
I
题意
给定一个1e5个点的无向图，共有1e5次询问，每次给出一组点集，求该点集构成的联通块数量。数据保证所有询问点集的总点数不超过1e5。
题解
题解链接
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int S=400; //sqrt(n)
const int INF=0x3f3f3f3f;
int n,e,p;
int u[maxn],v[maxn];
int a[maxn],vis[maxn];
vector<int>g[maxn];
int du[maxn];
int f[maxn];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void solve(){
rep(i,1,e){
if(du[u[i]]<=S) g[u[i]].push_back(v[i]);
if(du[v[i]]<=S) g[v[i]].push_back(u[i]);
if(du[u[i]]>S&&du[v[i]]>S) g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]);
}
rep(i,1,n) f[i]=i;
while(p--){
int k;
scanf("%d",&k);
rep(i,1,k) scanf("%d",&a[i]),vis[a[i]]=1;
int ans=k;
rep(i,1,k){
int x=find(a[i]);
rep0(j,0,g[a[i]].size()){
int y=g[a[i]][j];
if(!vis[y]) continue;
// D(a[i]);D(y);E;
y=find(g[a[i]][j]);
if(x!=y) f[y]=x,ans--; //direct graph need add edge y->x, not x->y
}
}
printf("%d\n",ans);
rep(i,1,k) vis[a[i]]=0,f[a[i]]=a[i];
}
}
int main() {
// ios::sync_with_stdio(false);
// freopen("I.in","r",stdin);
scanf("%d%d%d",&n,&e,&p);
rep(i,1,e) scanf("%d%d",&u[i],&v[i]),du[u[i]]++,du[v[i]]++;
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2020牛客国庆集训派对2
A
题意
给定一个1500个点的约瑟夫环，求最后一个存活的人的编号。
题解
刘汝佳《算法竞赛入门经典训练指南》上有关于本题的递推，不再赘述。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1500+5;
const int INF=0x3f3f3f3f;
int n,m;
int f[maxn];
void solve(){
memset(f,0,sizeof(f));
f[1]=0;
rep(i,2,n) f[i]=(f[i-1]+m)%i;
int ans=(f[n]+1)%n;
if(ans<=0) ans+=n;
cout<<ans<<endl;
}
int main() {
// ios::sync_with_stdio(false);
// freopen("A.in","r",stdin);
while(cin>>n>>m){
if(!n&&!m) break;
solve();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
B
题意
给定一个1e5个点的无向图，有18条有向路径。求这些路径首尾依次连接的最短长度。
题解
因为只关心每条路径起点和终点，因此首先求出所有路径起点终点之间的最短路。于是剩下的18条路径是否经过的情况可以使用一个二进制数表示，继而想到使用状压DP求解。
具体转移方程可参考哈密顿路。
时间复杂度。
代码如下
/*
*/
#define method_2
#ifdef method_1
/*
*/
#endif
/*
attention that
in long long
INF should be 1e18
not 0x3f3f3f3f3f3f3f3f
this error make me sumbit for more than 20 times
*/
#ifdef method_2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
const int maxn=1e4+5;
const int maxm=2e4+5;
const int maxk=20;
const ll INF=1e18;
int n,m,k;
int tot=1,head[maxn];
struct node{
int from,to;
ll w;
}edge[maxm];
ll G[maxk][maxk];
void add(int from,int to,ll w){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].w=w;
}
int v[maxn];
ll d[maxn];
priority_queue<pii>q;
void dijkstra(int s){
// memset(d,INF,sizeof(d));
rep(i,1,n) d[i]=INF;
memset(v,0,sizeof(v));
while(q.size()) q.pop();
d[s]=0ll;
q.push(make_pair(0ll,s));
while(q.size()){
int x=q.top().second;q.pop();
if(v[x]) continue;
v[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;ll w=edge[i].w;
if(d[y]>d[x]+w){
d[y]=d[x]+w;
q.push(make_pair(-d[y],y));
}
}
}
}
int f[maxk],t[maxk];
ll g[maxk][1<<maxk];
void dp(){
rep(i,0,k) rep(j,0,(1<<k)) g[i][j]=INF;
rep(i,1,k){
g[i][1<<i-1]=G[i][i];
// D(G[i][i]);E;
}
/*
rep0(j,0,1<<k){
rep(i,1,k){
if((j&(1<<i-1))==0) continue;
rep(lst,1,k){
if(lst==i) continue;
if((j&(1<<lst-1))==0) continue;
g[i-1][j]=min(g[i-1][j],g[lst-1][j&(~(1<<i-1))]+G[i][lst]+G[i][i]);
}
}
}
*/
rep0(j,0,(1<<k)){
rep(i,1,k){
if((j&(1<<i-1))==0) continue;
rep(lst,1,k){
if((j&(1<<lst-1))) continue;
g[lst][j|(1<<lst-1)]=min(g[lst][j|(1<<lst-1)],g[i][j]+G[i][lst]+G[lst][lst]);
}
}
}
ll ans=INF;
rep(i,1,k) ans=min(ans,g[i][(1<<k)-1]);
if(ans!=INF) printf("%lld",ans);
else printf("-1");
}
void solve(){
memset(G,INF,sizeof(G));
rep(i,1,k){
dijkstra(f[i]);
rep(j,1,k) G[i][j]=d[t[j]];
}
dp();
}
int main() {
// ios::sync_with_stdio(false);
// freopen("B.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
int from,to;
ll w;
rep(i,1,m) scanf("%d%d%lld",&from,&to,&w),add(from,to,w),add(to,from,w);
rep(i,1,k) scanf("%d%d",&f[i],&t[i]);
solve();
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
C
题意
给定到
个数字，求存在多少个极大子集，满足其中任意两个数不相邻。
题解
DFS模板题。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
int f[]={0,0,0,1,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465,616,816,1081,1432,1897,2513,3329,4410,5842,7739,10252,13581,17991,23833,31572,41824,55405,73396,97229,128801,170625,226030,299426,396655,525456,696081,922111,1221537,1618192,2143648,2839729,3761840,4983377,6601569,8745217,11584946,15346786,20330163,26931732,35676949,47261895,62608681,82938844,109870576,145547525,192809420,255418101,338356945,448227521,593775046,786584466,1042002567,1380359512,1828587033};
int n;
ll dfs(int x){
if(x>n) return 0;
if(x==n||x==n-1) return 1;
ll res=0;
res+=dfs(x+2)+dfs(x+3);
return res;
}
void solve(){
ll ans=0ll;
ans+=dfs(1)+dfs(2);
printf("%lld,",ans);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("C.in","r",stdin);
// freopen("C.out","w",stdout);
// rep(i,4,76) n=i,solve();
int kase=0;
while(cin>>n&&n) cout<<"Case #"<<++kase<<": "<<f[n]<<endl;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
D
题意
求MST。
题解
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
mst模板题。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,tot,ans,f[maxn],m;
struct node{
int from,to,c;
bool operator<(const node& h)const{return c<h.c;}
}edge[maxn*maxn];
void add(int from,int to,int c){
edge[++tot].from=from,edge[tot].to=to,edge[tot].c=c;
}
void init(){
tot=0,ans=0;
for(int i=1;i<=n;i++) f[i]=i;
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void kruskal(){
sort(edge+1,edge+m+1);
int cnt=0;
rep(i,1,m){
if(cnt>=n-1) break;
int x=edge[i].from,y=edge[i].to,c=edge[i].c;
x=find(x),y=find(y);
if(x!=y){
f[x]=y;ans+=c;cnt++;
}
}
}
int main() {
// freopen("D.in","r",stdin);
int T;
cin>>T;
rep(kase,1,T){
printf("Case #%d: ",kase);
cin>>n>>m;
init();
int from,to,temp;
rep(i,1,m) cin>>from>>to>>temp,add(from,to,temp);
kruskal();
printf("%d meters\n",ans);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
E
题意
模拟矩阵乘法。
题解
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20+5;
const int INF=0x3f3f3f3f;
int n,m,p,q;
ll a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
void mul(){
rep(i,1,m) rep(j,1,q) rep(k,1,n) c[i][j]+=a[i][k]*b[k][j];
}
void solve(){
memset(c,0,sizeof(c));
if(n!=p) {printf("undefined\n");return;}
mul();
rep(i,1,m){
printf("| ");
rep(j,1,q) printf("%lld ",c[i][j]);
printf("|\n");
}
}
int main() {
// ios::sync_with_stdio(false);
// freopen("E.in","r",stdin);
int kase=0;
while(scanf("%d%d%d%d",&m,&n,&p,&q)==4&&m&&n&&p&&q){
printf("Case #%d:\n",++kase);
rep(i,1,m) rep(j,1,n) scanf("%lld",&a[i][j]);
rep(i,1,p) rep(j,1,q) scanf("%lld",&b[i][j]);
solve();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
F
题意
求下面代码的结果。
sum = 0
for r1 = 0 to N-1
for c1 = 0 to N-1
for r2 = r1+1 to N
for c2 = r2+1 to N
sum = sum + (r2-r1)*(c2-c1)
print(sum)
题解
打表找规律即可。
时间复杂度。
代码如下
T=int(input())
while T>0:
T=T-1
ans=int(1)
n=int(input())
ans*=int(n*(n+1)*(n+2)/6)
ans*=ans
print(ans)
G
题意
模拟题。
题解
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
int n;
void solve(){
double res=0.0;
rep(i,1,n){
double c,b,l,nasi;
double sum=0.0;
cin>>c>>b>>l>>nasi;
sum+=c+b+l;
res-=8.0*sum/85.0;
res+=nasi*0.6;
res+=0.8*c+1.0*b+1.2*l;
res-=c*7.5/85.0+b*24.0/85.0+l*32.0/85.0;
}
printf("RM%.2lf\n",res);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("G.in","r",stdin);
int kase=0;
while(cin>>n&&n) cout<<"Case #"<<++kase<<": ",solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
J
题意
求斐波那契的第n项。
题解
模拟即可，注意加入高精度。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
const int MAXN = 550;
const int MAXNLEN = 130;
int F[MAXN][MAXNLEN];
char Fi[MAXN][MAXNLEN],ans[MAXN];
void Fibo() {
F[1][0] = 1;
F[2][0] = 1;
for(int i = 3; i <= 500; ++i) {
for(int j = 0; j <= 110; ++j) {
F[i][j] = F[i][j] + F[i-1][j] + F[i-2][j];
if(F[i][j] >= 10) {
F[i][j+1] += F[i][j]/10;
F[i][j] %= 10;
}
}
}
for(int i = 1; i <= 500; ++i) {
int j;
for(j = 110; j >= 0; j--)
if(F[i][j] == 0)
continue;
else
break;
int k = 0;
for(; j >= 0; j--)
Fi[i][k++] = F[i][j] + '0';
F[i][k] = '\0';
}
}
void solve() {
Fibo();
int x;
while(cin>>x){
if(x==-1) break;
printf("Hour: %d: %s cow(s) affected\n",x,Fi[x]);
}
}
int main() {
// ios::sync_with_stdio(false);
// freopen("J.in","r",stdin);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2020牛客国庆集训派对3
B
题意
给定一个200个点，400条边的无向图，第i条边的边权为，
为
之间随机分布的常数，求起点到终点的最短路的期望。（误差小于1e-4）
题解
因为误差范围较小，可以将分成1e-4份，每次求一遍最短路，累加后再除以1e-4即可。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<double,int>pii;
const int maxn=200+5;
const int maxm=400+5;
const int INF=0x3f3f3f3f;
int n,m,s,t;
double d[maxn];
int vis[maxn];
struct node{
int v,x,y;
node(){}
node(int _v,double _x,double _y){v=_v,x=_x,y=_y;}
};
vector<node>g[maxn];
priority_queue<pii>q;
void init(){
while(q.size()) q.pop();
rep(i,1,n) d[i]=1e18;
memset(vis,0,sizeof(vis));
}
double dij(double a){
init();
d[s]=0.0;
q.push(make_pair(0.0,s));
while(q.size()){
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=1;
rep0(i,0,g[x].size()){
int y=g[x][i].v;
double w1=g[x][i].x,w2=g[x][i].y;
if(d[y]>d[x]+w1+w2*a){
d[y]=d[x]+w1+w2*a;
q.push(make_pair(-d[y],y));
}
}
}
return d[t];
}
void solve(){
int T=100000;
double ans=0.0;
rep(i,0,T) ans+=dij(1.0*i/T);
printf("%.6lf",ans/(1.0*T));
}
int main() {
// ios::sync_with_stdio(false);
// freopen("B.in","r",stdin);
scanf("%d%d%d%d",&n,&m,&s,&t);
int u,v;
double x,y;
rep(i,1,m) scanf("%d%d%lf%lf",&u,&v,&x,&y),g[u].push_back(node(v,x,y)),g[v].push_back(node(u,x,y));
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
D
题意
给定两个内切圆和1e4个位于两圆中间的点，求一个同时内切于这两个圆的圆，使得覆盖的点最多。
题解
两个内切圆反演后得到的是两条直线，而点的反演在两条直线之间，所求圆反演后的圆心处于这两条直线的中线上。于是可以转化为这题的做法。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e4+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int T;
int n;
double R,r;
struct node{
double x,y;
node(){}
node(double _x,double _y){x=_x,y=_y;}
}p[maxn];
vector<node>v;
inline double sqr(double x){return x*x;}
int sgn(double x){
if(fabs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
bool cmp(node a,node b){
if(sgn(a.y-b.y)==0) return a.x>b.x; //1 is before -1 , considering there maybe more than two points appear at same position
return a.y<b.y;
}
void init(){
v.clear();
}
void solve(){
init();
double mid=(double)R+(double)(R*R)/(double)r;
double rr=(double)(R*R)/(double)r-(double)R;
rep(i,1,n){
ll x,y;
cin>>x>>y;
p[i].x=(double)(4ll*R*R*x)/(double)(x*x+y*y);
p[i].y=(double)(4ll*R*R*y)/(double)(x*x+y*y);
//点的反演
if(sgn(fabs(p[i].x-mid)-rr)==0){
v.push_back(node(1.0,p[i].y));
v.push_back(node(-1.0,p[i].y));
}
else if(sgn(fabs(p[i].x-mid)-rr)<0){
double h=sqrt(sqr(rr)-sqr(p[i].x-mid));
v.push_back(node(-1.0,p[i].y+h));
v.push_back(node(1, p[i].y-h));
}
else continue;
}
sort(v.begin(),v.end(),cmp);
int ans=0,cnt=0;
rep0(i,0,v.size()) cnt+=v[i].x,ans=max(ans,cnt);
printf("%d\n",ans);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("D.in","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%lf%lf",&n,&R,&r);
solve();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
F
题意
求一棵无根树中度数为1的节点数。
题解
模拟即可。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int n;
int x,y;
int v[maxn];
void solve(){
rep(i,1,n-1) scanf("%d%d",&x,&y),v[x]++,v[y]++;
int ans=0;
rep(i,1,n) if(v[i]==1) ans++;
printf("%d",ans);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("F.in","r",stdin);
scanf("%d",&n);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
J
题意
给定一个长度为1e5的序列，每次可以选择其中个数字，将他们全体减一。求最多能进行多少次操作。
题解
考虑二分答案，对于大于等于
的数字，可以分配到
组里，贡献即为
。对于小于
的数字，则必须全部用完，贡献即为它本身。若所有数字的贡献和不小于
，那么当前
即合法。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3e5+5;
const ll INF=0x7fffffffffffffffll;
int n,m,T;
ll a[maxn],sum;
void init(){
sum=0ll;
}
bool check(ll mid){
ll res=0;
rep(i,1,n) res+=min(a[i],mid);
return res>=mid*m;
}
void solve(){
sort(a+1,a+n+1);
reverse(a+1,a+n+1);
ll l=0,r=sum/m+1;
while(l<r){
ll mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%lld\n",l);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("J.in","r",stdin);
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%lld",&a[i]),sum+=a[i];
solve();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2020牛客国庆集训派对4
B
题意
求1e3个数字的最长等差子序列。
题解
考虑DP，设表示
的最长等差子序列（选取
和
）。于是存在转移方程
。这样直接暴力枚举三个维度，时间复杂度过高。但注意到符合条件的
和
是分布在
左右的，所以可以枚举
，然后用两个指针往
的两侧移动，符合条件时更新答案。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int INF=0x3f3f3f3f;
int n;
int a[maxn],f[maxn][maxn];
void solve(){
sort(a+1,a+n+1);
rep(i,1,n) rep(j,i+1,n) f[i][j]=2;
int ans=2;
rep(i,2,n-1){
int k=i-1,j=i+1;
while(k>=1&&j<=n){
if(a[k]+a[j]<2*a[i]) j++;
else if(a[k]+a[j]>2*a[i]) k--;
else{
f[i][j]=max(f[i][j],f[k][i]+1);
ans=max(ans,f[i][j]);
k--,j++;
}
}
}
printf("%d",ans);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("B.in","r",stdin);
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
D
题意
给出两个长度为5000的 01 串a和b，求最短的 01 串 t ，使得 t 不是 a 和 b 的子序列，若有多个答案则输出字典序最小的。
题解
题解链接
代码如下
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
void solve() {
}
int main() {
// ios::sync_with_stdio(false);
freopen("D.in","r",stdin);
return 0;
}
#endif
#ifdef method_2
/*
*/
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=4e3+100;
char s1[N],s2[N];
int nt1[N][2],nt2[N][2],len1,len2;
int dp[N][N],path[N][N];
int dfs(int x,int y) {
if(x==len1+1&&y==len2+1)
return dp[x][y]=0;
if(dp[x][y]!=-1)
return dp[x][y];
int ans1=dfs(nt1[x][0],nt2[y][0]); // chose 0
int ans2=dfs(nt1[x][1],nt2[y][1]); // chose 1
if(ans1<=ans2)
path[x][y]=0;
else
path[x][y]=1;
// D(x);D(y);D(ans1);D(ans2);E;
return dp[x][y]=min(ans1,ans2)+1;
}
void print(int x,int y) {
if(x==len1+1&&y==len2+1)
return;
putchar(path[x][y]+'0');
print(nt1[x][path[x][y]],nt2[y][path[x][y]]);
}
void init(char s[],int &len,int nt[][2]) {
len=strlen(s+1);
nt[len+1][0]=nt[len+1][1]=len+1;
nt[len][0]=nt[len][1]=len+1;
for(int i=len-1; i>=0; i--) {
nt[i][0]=nt[i+1][0];
nt[i][1]=nt[i+1][1];
nt[i][s[i+1]-'0']=i+1;
}
}
int main() {
// freopen("D.in","r",stdin);
scanf("%s%s",s1+1,s2+1);
init(s1,len1,nt1);
init(s2,len2,nt2);
memset(dp,-1,sizeof(dp));
dfs(0,0);
print(0,0);
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
F
题意
给定长度为1e5的序列，每次可以交换两个相邻元素，求将其变成合唱队形（先升序后降序）的最小次数。
题解
考虑每次移动当前最小的数字，那么它向左向右移动到两端的次数都可以利用树状数组确定。
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn];
int b[maxn],cnt;
int l[maxn],r[maxn];
int c[maxn];
void add(int x){
for(;x<=cnt;x+=x&-x) c[x]++;
}
int ask(int x){
int res=0;
for(;x;x-=x&-x) res+=c[x];
return res;
}
void solve(){
sort(b+1,b+n+1);
cnt=unique(b+1,b+n+1)-b-1;
rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
// rep(i,1,n) D(a[i]);
rep(i,1,n){
l[i]=ask(a[i]);
add(a[i]);
}
// rep(i,1,n) D(a[i]);E;
// rep(i,1,n) D(l[i]);E;
memset(c,0,sizeof(c));
rrep(i,n,1){
r[i]=ask(a[i]);
add(a[i]);
}
// rep(i,1,n) D(r[i]);E;
ll ans=0ll;
rep(i,1,n){
ans+=ll(min(i-1-l[i],n-i-r[i]));
}
printf("%lld",ans);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("F.in","r",stdin);
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]),b[i]=a[i];
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
H
题意
给出一棵1e5个节点的树，每个节点都有一个颜色，现在需要执行1e5次操作，每次操作分为如下两种类型：
Q x：回答所有颜色为 x 的节点构成的连通子图含有的最少边数
U x y：将点 x 的颜色修改为 y
题解
题解链接
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int maxlogn=20;
const int INF=0x3f3f3f3f;
struct node{
int from,to;
}edge[maxn<<1];
int head[maxn],tot=1;
void add(int from,int to){
edge[++tot].from=head[from],edge[tot].to=to,head[from]=tot;
}
int n,m,c[maxn];
int dfn[maxn],cnt=0;
struct Scmp{
bool operator()(int x,int y) {return dfn[x]<dfn[y]; }
};
set<int,Scmp>S[maxn];
void dfs(int x,int fa){
dfn[x]=++cnt;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(y==fa) continue;
dfs(y,x);
}
}
queue<int>q;
int t;
int d[maxn],f[maxn][maxlogn];
void bfs(int st){
d[st]=1;q.push(st);
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(d[y]) continue;
d[y]=d[x]+1,f[y][0]=x;
rep(j,1,t) f[y][j]=f[f[y][j-1]][j-1];
q.push(y);
}
}
// rep(i,1,n) D(d[i]);E;
}
int lca(int x,int y){
if(d[x]>d[y]) swap(x,y);
rrep(i,t,0) if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
rrep(i,t,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int dis(int x,int y){
int res=d[x]+d[y]-2*d[lca(x,y)];
// D(x);D(d[x]);D(y);D(d[y]);D(lca(x,y));D(res);E;
return res;
}
int ans[maxn];
void update(int x,int flag){
if(flag==-1) S[c[x]].erase(x);
set<int,Scmp>::iterator it=S[c[x]].lower_bound(x),nxt,pre;
// D(c[x]);D(x);E;
if(S[c[x]].empty()) ans[c[x]]=0;
else if(it==S[c[x]].begin()||it==S[c[x]].end()){
// D(*S[c[x]].begin());D(*S[c[x]].rbegin());D(*it);E;
ans[c[x]]+=flag*dis(*S[c[x]].begin(),x);
ans[c[x]]+=flag*dis(*S[c[x]].rbegin(),x);
ans[c[x]]-=flag*dis(*S[c[x]].begin(),*S[c[x]].rbegin());
// D(ans[c[x]]);E;
}
else{
nxt=it,pre=--it;
// D(*nxt);D(*pre);E;
ans[c[x]]+=flag*dis(*nxt,x);
ans[c[x]]+=flag*dis(*pre,x);
ans[c[x]]-=flag*dis(*pre,*nxt);
}
if(flag==1) S[c[x]].insert(x);
}
void solve(){
char op[2];
int x,y;
while(m--){
scanf("%s",op);
if(op[0]=='Q'){
scanf("%d",&x);
if(S[x].empty()) printf("-1\n");
else printf("%d\n",ans[x]/2);
}
if(op[0]=='U'){
scanf("%d%d",&x,&y);
update(x,-1);
c[x]=y;
update(x,1);
}
}
}
int main() {
// ios::sync_with_stdio(false);
// freopen("H.in","r",stdin);
scanf("%d",&n);
t=int(log(n)/log(2))+1;
int from,to;
rep(i,1,n-1) scanf("%d%d",&from,&to),add(from,to),add(to,from);
dfs(1,-1);
bfs(1);
rep(i,1,n) scanf("%d",&c[i]),update(i,1);
scanf("%d",&m);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
I
题意
求田忌赛马的一组字典序最大的解。（)
题解
题解链接
代码如下
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
void solve(){
}
int main() {
// ios::sync_with_stdio(false);
freopen("I.in","r",stdin);
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;++i)
#define Fd(i,a,b) for(I i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 5010
using namespace std;
I rd(I &x){
x=0;I w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=w;
}
I n,a[N],b[N],c[N],d[N],t,s,l,r,k,mid,ans,tot;
I cmp(I x,I y){return x>y;}
I check(I x,I y){
I k=0,p=0;
F(i,1,s){
if(k+1==x) k++;
if(k<s&&b[k+1]>c[i]) k++,p++;
}
return p+tot+y==t;
}
I main(){
// freopen("I.in","r",stdin);
scanf("%d",&n);
F(i,1,n){scanf("%d",&a[i]),c[i]=-a[i];}
sort(c+1,c+1+n);
F(i,1,n) scanf("%d",&b[i]),c[i]=-c[i];
sort(b+1,b+1+n,cmp);
F(i,1,n) if(t<n&&b[t+1]>c[i]) t++;
s=n+1;
F(i,1,n-1){
s--;
F(j,1,s) if(c[j]==a[i]){c[j]=1e9;break;}
I k=s+1;
F(j,1,s) if(b[j]<=a[i]){k=j;break;}
l=1,r=k-1,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid,1)){ans=mid,r=mid-1;}
else l=mid+1;
}
if(!ans){
l=k,r=s;
while(l<=r){
mid=(l+r)>>1;
if(check(mid,0)){ans=mid,r=mid-1;}
else l=mid+1;
}
}
printf("%d ",b[ans]);
tot+=(b[ans]>a[i]);
F(j,ans,s-1) b[j]=b[j+1];
F(j,1,s) if(c[j]==1e9){
F(k,j,s-1) c[k]=c[k+1];
break;
}
}
printf("%d ",b[1]);
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
2020牛客国庆集训派对5
B
题意
给定一个长度为1e5的字符串，求它有多少个子串，重新排列后可以形成回文子串。
题解
一个字符串为回文串的条件是，它的所有字符中，至多只有一个字符出现次数为奇数。因此可以考虑使用异或运算维护每个字符出现次数的奇偶性。这样从左向右扫描一遍后，对于每个前缀异或值，它出现的次数即为对答案的贡献。（因为每出现一次，就意味着从上一个位置到当前位置的子串是一个合法子串）
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3e5+5;
const int maxm=52+5;
const int INF=0x3f3f3f3f;
int n;
char s[maxn];
inline int ID(char ch){
if(ch>='A'&&ch<='Z') return ch-'A';
else return ch-'a'+26;
}
map<ll,int>mp;
void solve(){
ll res=0ll;
mp.clear();
mp[0]=1;
ll sum=0;
rep(i,1,n){
int ch=ID(s[i]);
sum^=(1ll<<ch);
res+=ll(mp[sum]);
rep0(j,0,52) res+=ll(mp[sum^(1ll<<j)]);
mp[sum]++;
}
printf("%lld",res);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("B.in","r",stdin);
scanf("%d",&n);
scanf("%s",s+1);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
H
题意
模拟题。
题解
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int n;
int len;
string s,t;
vector<string>res;
bool check(){
int len2=t.length();
if(len!=len2) return false;
rep0(i,0,len){
if(s[i]!='*'&&s[i]!=t[i]) return false;
}
return true;
}
void solve(){
len=s.length();
int cnt=0;
res.clear();
while(n--){
cin>>t;
if(check()) cnt++,res.push_back(t);
}
cout<<cnt<<endl;
rep0(i,0,res.size()) cout<<res[i]<<endl;
}
int main() {
// ios::sync_with_stdio(false);
// freopen("H.in","r",stdin);
cin>>s>>n;
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
K
题意
模拟题。
题解
时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int n,m;
struct node{
int a,b;
}c[maxn];
int get(int i,int t){
int times=t/(c[i].b-c[i].a);
if(times&1) return c[i].b-t%(c[i].b-c[i].a);
return c[i].a+t%(c[i].b-c[i].a);
}
void solve(){
int x,y,t;
while(m--){
scanf("%d%d%d",&x,&y,&t);
int cnt=0;
rep(i,1,n){
int pos=get(i,t);
// D(i);D(pos);E;
if(pos>=x&&pos<=y) cnt++;
}
printf("%d\n",cnt);
}
}
int main() {
// ios::sync_with_stdio(false);
// freopen("K.in","r",stdin);
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d%d",&c[i].a,&c[i].b);
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
