Codeforces 1058 Div 2 (A-F)
在 Print 之前
突然發(fā)現(xiàn)已經(jīng)很久沒寫過博客了，前一晚才搭好這個博客樣式，正好晚上熬夜打一下 Div 2。
賽時3941分，排在471位，T5雙指針寫掛了，調(diào)了一個小時沒調(diào)出來。
A - MEX Partition
水題一道。
不難發(fā)現(xiàn)，答案就是 \(MEX(A)\)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=2e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,a[N];
inline void solve() {
n=read();
ll cnt=0;
for(ll i=1;i<=n;i++) {
a[i]=read();
}
sort(a+1,a+1+n);
for(ll i=1;i<=n;i++) {
if(a[i]!=cnt) {
break;
}
else {
while(a[i]==a[i+1]) {
i++;
}
cnt++;
}
}
print(cnt);
puts("");
}
praise_long_long main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll T=1;
T=read();
while(T--) {
solve();
}
return 0;
}
/**/
B - Distinct Elements
其實(shí)不難發(fā)現(xiàn)，當(dāng) \(a_i\) 在之前沒有出現(xiàn)過時，則有 \(b_i-b_{i-1}=i\)，這樣我們就可以給 \(a_i\) 安一個新的數(shù)。
反之若 \(b_i-b_{i-1} \not = i\)，則 \(a_i\) 必定與 \(a_{i-(b_i-b_{i-1})}\) 相同。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=2e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,a[N],b[N];
set<ll> st;
inline void solve() {
n=read();
st.clear();
for(ll i=1;i<=n;i++) {
b[i]=read();
st.insert(i);
}
for(ll i=1;i<=n;i++) {
if(b[i]==b[i-1]) {
a[i]=a[i-1];
}
else {
a[i]=b[i]-b[i-1];
}
ll lt=i-a[i];
if(!lt) {
a[i]=(*st.begin());
st.erase(st.begin());
}
else {
a[i]=a[lt];
}
}
for(ll i=1;i<=n;i++) {
cout<<a[i]<<' ';
}
puts("");
}
praise_long_long main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll T=1;
T=read();
while(T--) {
solve();
}
return 0;
}
/**/
C - Reverse XOR
拿 \(6\) 舉例子，它的二進(jìn)制是 \(110_2\)，我們發(fā)現(xiàn)只需在開頭加上一個 \(0\) 或在結(jié)尾減去一個 \(0\) 即可。
所以可以刪去末尾的 \(0\) 來完成或者在開頭添加 \(0\) 即可。
注意奇數(shù)的回文串中間一位應(yīng)為 \(0\)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=2e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,cnt;
string num,sum;
inline void solve() {
n=read();
cnt=0;
sum="";
num="";
while(n) {
num+=(char)(n%2+'0');
n/=2;
cnt++;
}
reverse(num.begin(),num.end());
for(ll i=cnt;i<=cnt*2;i++) {
string t=sum+num;
string kl=t;
reverse(kl.begin(),kl.end());
if(t==kl) {
if(i&1) {
if(t[i/2]=='0') {
puts("YES");
return ;
}
}
else {
puts("YES");
return ;
}
}
sum+='0';
}
puts("NO");
}
praise_long_long main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll T=1;
T=read();
while(T--) {
solve();
}
return 0;
}
/**/
D - MAD Interactive Problem
我們可以發(fā)現(xiàn)當(dāng)我們查詢第 \(i\) 位之前的查詢?yōu)?\(0\)，但第 \(i\) 位查詢時不為 \(0\)，那么第 \(i\) 位肯定是查詢所得的數(shù)。
同理，當(dāng)我們確定了一個 \(n\) 的排列后可以用同樣的方法求出 \(i\) 號元素第一次出現(xiàn)的位置。
用 \(2*n\) 次訪問出第二個 \(i\) 的位置，然后再用 \(n\) 次查詢來鎖定第一個位置，總查詢次數(shù)是 \(3*n\)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=6e2+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,a[N],num[N],cnt,vis[N];
inline void input() {
cout<<"? "<<cnt;
cout.flush();
for(ll i=1;i<=cnt;i++) {
cout<<' '<<num[i];
cout.flush();
}
puts("");
cout.flush();
}
inline void input1() {
for(ll i=1;i<=cnt;i++) {
num[i]=vis[i];
}
input();
}
inline void solve() {
n=read();
cnt=0;
num[++cnt]=1;
a[1]=0;
for(ll i=2;i<=2*n;i++) {
a[i]=0;
num[++cnt]=i;
input();
ll sum=read();
if(sum) {
a[i]=sum;
vis[sum]=i;
cnt--;
}
}
cnt=n;
for(ll i=1;i<=2*n;i++) {
if(a[i]) {
continue;
}
vis[++cnt]=i;
input1();
ll sum=read();
a[i]=sum;
cnt--;
}
cout<<'!';
cout.flush();
for(ll i=1;i<=2*n;i++) {
cout<<' '<<a[i];
cout.flush();
}
puts("");
cout.flush();
}
praise_long_long main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll T=1;
T=read();
while(T--) {
solve();
}
return 0;
}
/**/
E - Rectangles
事實(shí)上 \(O(n^2 m^2)\) 的復(fù)雜度還是挺好想的，只需確定矩形的上下界，然后找到這區(qū)間內(nèi)的所有可以對應(yīng)的點(diǎn)，更新它們兩兩之間的點(diǎn)的最小值。
但如何把復(fù)雜度壓下來呢？
不難發(fā)現(xiàn)，最費(fèi)事情的就是更新最小值，那有沒有辦法降低這個復(fù)雜度呢？
事實(shí)上，我們可以用一個十分經(jīng)典的 \(min\) 前綴和來實(shí)現(xiàn)。
因?yàn)槲覀兪菑纳贤聛硭阉鞯模陨厦娴牟糠质遣粫桓碌摹?/p>
而下面部分，如果說這一列的后面的值比當(dāng)前位置的小，又因?yàn)楫?dāng)前位置到矩形的上方是可以被后面包含的，那么就把這一位更新為后一位。
這樣的復(fù)雜度為 \(O(n^2 m)\)
但當(dāng) \(n\) 很大時復(fù)雜度爆表，但反向枚舉 \(m\) 卻更優(yōu)，所以當(dāng) \(n>m\) 時就枚舉 \(m\) 即可，思路與上方一致。
最終復(fù)雜度：\(O(min(n,m)nm)\)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=2.5e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,m;
vector<ll> num;
inline void solve() {
n=read(),m=read();
vector<ll> v[min(n,m)+5];
ll ans[n+5][m+5];
for(ll i=1;i<=min(n,m);i++) {
v[i].clear();
}
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=m;j++) {
ans[i][j]=inf;
}
}
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=m;j++) {
char c;
cin>>c;
if(c=='1') {
if(n<=m) {
v[i].push_back(j);
}
else {
v[j].push_back(i);
}
}
}
}
if(n<=m) {
for(ll u=1;u<=n;u++) {
if(v[u].size()<2) {
continue;
}
for(ll d=u+1;d<=n;d++) {
if(v[d].size()<2) {
continue;
}
vector<ll> al=v[u],bl=v[d];
ll l=0,r=0;
num.clear();
while(l<al.size()&&r<bl.size()) {
if(al[l]==bl[r]) {
num.push_back(bl[r]);
l++;
r++;
}
else if(al[l]<bl[r]) {
l++;
}
else {
r++;
}
}
// cout<<u<<' '<<d<<endl;
// for(auto it : num) {
// cout<<it<<' ';
// }
// puts("");
if(num.size()<2) {
continue;
}
for(ll i=1;i<num.size();i++) {
for(ll j=num[i-1];j<=num[i];j++) {
ans[d][j]=min(ans[d][j],(d-u+1)*(num[i]-num[i-1]+1));
}
}
}
for(ll i=n-1;i>=u;i--) {
for(ll j=1;j<=m;j++) {
ans[i][j]=min(ans[i][j],ans[i+1][j]);
}
}
}
}
else {
for(ll u=1;u<=m;u++) {
if(v[u].size()<2) {
continue;
}
for(ll d=u+1;d<=m;d++) {
if(v[d].size()<2) {
continue;
}
vector<ll> al=v[u],bl=v[d],cl;
ll l=0,r=0;
num.clear();
while(l<al.size()&&r<bl.size()) {
if(al[l]==bl[r]) {
num.push_back(bl[r]);
l++;
r++;
}
else if(al[l]<bl[r]) {
l++;
}
else {
r++;
}
}
if(num.size()<2) {
continue;
}
for(ll i=1;i<num.size();i++) {
for(ll j=num[i-1];j<=num[i];j++) {
ans[j][d]=min(ans[j][d],(d-u+1)*(num[i]-num[i-1]+1));
}
}
}
for(ll i=m-1;i>=u;i--) {
for(ll j=1;j<=n;j++) {
ans[j][i]=min(ans[j][i],ans[j][i+1]);
}
}
}
}
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=m;j++) {
if(ans[i][j]==inf) {
ans[i][j]=0;
}
print(ans[i][j]);
putchar(' ');
}
puts("");
}
}
praise_long_long main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll T=1;
T=read();
while(T--) {
solve();
}
return 0;
}
F - Twin Polynomials
這題說實(shí)話只要想明白了就很簡單，但想歪了……
我們發(fā)現(xiàn)，如果 \(a_i\) 有值但 \(a_{a_i}\) 沒值時，\(a_{a_i}\) 必定等于 \(i\)。
如果 \(a_i\) 有值 \(a_{a_i}\) 也有值時，若 \(a_{a_i} \not = i\) 時，則這個方案無效，否則繼續(xù)。
但剩下的怎么辦呢？
不難想到，想讓 \(a_i\) 合法，他只有可能等于 \(0\)、等于 \(i\)、連向其他一個點(diǎn)這三種情況。
就這樣我們不難想到這是個 \(dp\)。
設(shè) \(f_i\) 表示當(dāng)有i個點(diǎn)剩余的合法方案數(shù)，等于 \(0\) 就是加上 \(f_{i-1}\)，等于自己也是加上 \(f_{i-1}\)，而選擇另一個點(diǎn)就是加上 \((i-1)*f_{i-2}\)。
所以狀態(tài)轉(zhuǎn)移就是：
\[f_i=2*f_{i-1}+(i-1)*f_{i-2}
\]
注意 \(a_n\) 不能為 \(0\)，所以如果最后 \(a_n=-1\) 答案需要減掉 \(f_{cnt-1}\)，其中 \(cnt\) 為剩余的 \(a_i=-1\) 的個數(shù)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=4e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,a[N],cnt,f[N];
inline void solve() {
n=read();
cnt=0;
for(ll i=0;i<=n;i++) {
a[i]=read();
}
bool fl=0;
for(ll i=1;i<=n;i++) {
if(a[i]==-1||a[i]==0) {
continue;
}
if(a[i]>n||(i!=a[a[i]]&&a[a[i]]!=-1)) {
fl=1;
break;
}
if(a[a[i]]==-1) {
a[a[i]]=i;
}
}
if(fl) {
puts("0");
return ;
}
for(ll i=1;i<=n;i++) {
if(a[i]==-1) {
cnt++;
}
}
f[0]=1,f[1]=2;
for(ll i=2;i<=cnt;i++) {
f[i]=f[i-1]*2+(i-1)*f[i-2];
f[i]%=mod;
}
if(a[n]==-1) {
f[cnt]-=f[cnt-1];
f[cnt]+=mod;
f[cnt]%=mod;
}
print(f[cnt]);
puts("");
}
praise_long_long main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll T=1;
T=read();
while(T--) {
solve();
}
return 0;
}
/**/
浙公網(wǎng)安備 33010602011771號