直到\(7:58\)才知道今天\(8:00\)有\(AtCoder\)的菜鸡来写题解啦.
C - pushpush
题目:
给定一个长为\(n\)的序列,第\(i\)次操作做如下的事 :
- 将\(a_i\)插入到数组\(b\)的尾部.
- 翻转数组\(b\).
一开始数组\(b\)为空，进行完所有操作后输出\(b\)数组。
\(n \leq 2\times 10^5,0\leq a_i \leq 10^9\)
题解:
用一个双端队列模拟就好了.
#include#include #include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;static char ch;static bool flag;flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}#define rg register int#define rep(i,a,b) for(rg i=(a);i<=(b);++i)#define per(i,a,b) for(rg i=(a);i>=(b);--i)deque q;int main(){ int n;read(n); int p = 1,x; if(n&1) p ^= 1; rep(i,1,n){ read(x); if(p&1) q.push_back(x); else q.push_front(x); p ^= 1; } while(!q.empty()){ printf("%d",q.front()); q.pop_front(); if(q.empty()) putchar('\n'); else putchar(' '); } return 0;}
D - 11
题目:
给定一个长度为\(n+1\)的序列\(a\)，每个元素都在\([1,n]\)范围内且只有一种元素出现了两次.
对于\(k = 1 \space .. n+1\),求出长度为\(k\)的本质不同的子序列个数.\(n \leq 10^5\)
题解:
如果所有的元素都不互相同那么\(ans_k = {n+1 \choose k}\)
那么处理出出现了两次的元素的下标\(p1,p2\),设\(d = p2 - p1 + 1\) 那么可以发现所有本质相同的子序列一定是因为这两个元素。 所以容易发现重复的方案为\(n+1-d \choose k-1\) 所以有: \(ans_k = {n+1 \choose k} - {n+1-1 \choose k-1}\) 预处理组合数做到单点\(O(1)\)#include#include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;static char ch;static bool flag;flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}#define rg register int#define rep(i,a,b) for(rg i=(a);i<=(b);++i)#define per(i,a,b) for(rg i=(a);i>=(b);--i)const int maxn = 100010;const int mod = 1e9+7;int frac[maxn],inv[maxn];inline int qpow(int x,int p){ int ret = 1; for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x % mod; return ret;}inline int C(int n,int m){ if(m > n) return 0; return 1LL*frac[n]*inv[m]%mod*inv[n-m]%mod;}int last[maxn];int main(){ int n;read(n);++ n; frac[0] = 1; rep(i,1,n) frac[i] = 1LL*i*frac[i-1] % mod; inv[n] = qpow(frac[n],mod-2); per(i,n-1,0) inv[i] = 1LL*inv[i+1]*(i+1) % mod; int x,p1,p2; rep(i,1,n){ read(x); if(last[x] != 0){ p1 = last[x]; p2 = i; } last[x] = i; } int num = n - (p2 - p1 + 1); rep(k,1,n){ int ans = C(n,k) - C(num,k-1); if(ans < 0) ans += mod; printf("%d\n",ans); } return 0;}
E - guruguru
题目:
现在有一个数字\(x\)和一个上限\(m\),进行第一种操作可以使\(x \to x+1\),若当前的\(x = m\)那么第一种操作会\(x \to 1\).
第二种操作会使得\(x \to k\)其中\(k\)是一个常量. 现在给定一个长为\(n\)的序列\(a\),你需要让这个数依次变成\(a_2,a_3,...,a_n\) 初始的数为\(a_1\),你需要确定一个常数\(k\)使得最少的操作次数最小. $n,m \leq 10^5 $
题解:
容易发现对于每两个相邻的数\(a_i,a_{i+1}\)，对整个\(k\)选择区间造成的影响总是可以拆成:
- 一个常数数列和两个等差数列
- 一个等差数列和两个常数数列
这个东西直接拆开用线段树维护即可。
#include#include #include using namespace std;typedef long long ll;inline void read(ll &x){ x=0;static char ch;static bool flag;flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}#define rg register int#define rep(i,a,b) for(rg i=(a);i<=(b);++i)#define per(i,a,b) for(rg i=(a);i>=(b);--i)const ll maxn = 100010;ll a[maxn],d[maxn],n,m;ll lazy[maxn<<2],tag[maxn<<2],num[maxn<<2];void modify(ll rt,ll l,ll r,ll L,ll R,ll v){ if(L <= l && r <= R){ lazy[rt] += v; return ; } ll mid = l+r >> 1; if(L <= mid) modify(rt<<1,l,mid,L,R,v); if(R > mid) modify(rt<<1|1,mid+1,r,L,R,v);}void insert(ll rt,ll l,ll r,ll L,ll R,ll s){ if(L <= l && r <= R){ tag[rt] += s;++ num[rt]; return ; } ll mid = l+r >> 1; if(R <= mid) insert(rt<<1,l,mid,L,R,s); else if(L > mid) insert(rt<<1|1,mid+1,r,L,R,s); else{ insert(rt<<1,l,mid,L,mid,(R-mid)+s); insert(rt<<1|1,mid+1,r,mid+1,R,s); }}ll res;void query(ll rt,ll l,ll r,ll p){ res += lazy[rt]; res += tag[rt] + num[rt]*(r - p); if(l == r) return ; ll mid = l+r >> 1; if(p <= mid) query(rt<<1,l,mid,p); else query(rt<<1|1,mid+1,r,p);}int main(){ read(n);read(m); rep(i,1,n){ read(a[i]); if(i > 1){ ll x = (a[i] - a[i-1] + m) % m; if(a[i] > a[i-1]){ modify(1,1,m,1,a[i-1],x); if(a[i]+1 <= m) modify(1,1,m,a[i]+1,m,x); if(a[i-1]+1 <= a[i]) insert(1,1,m,a[i-1]+1,a[i],1); }else{ modify(1,1,m,a[i]+1,a[i-1],x); insert(1,1,m,1,a[i],1); if(a[i-1]+1 <= m) insert(1,1,m,a[i-1]+1,m,a[i]+1); } } } ll ans = 1LL << 60; rep(i,1,m){ res = 0;query(1,1,m,i); ans = min(ans,res); } printf("%lld\n",ans); return 0;}
做题经历
开眼看题发现\(T1\)一个双端队列就搞定了啊。
然后听到旁边的\(gls\)说第一题跟\(a+b\)差不多水吧. ... ... ... ... ... ... 然后发现\(gls\)注册的是\(Beginner\space Contest\)...\(shs\)不小心把\(T1\) \(Wa\)了一发.
\(T2\)大家都是一边过直接秒了.貌似\(T3\)只有我这个\(SB\)写了颗线段树。
$shs \space : $我就写的差分啊
$lrd \space : $差分不就行了，用个卵的线段树啊?我承认我写了个卵。。。
dalao 们都太强了！