感觉vpABC比vpCF好太多了，因为至少能开到算法题....

Tasks - AtCoder Beginner Contest 293

A - Swap Odd and Even

模拟

Code：

#include 
using namespace std;
#define int long long
using i64 = long long;
const int mxn=1e6+10;
const int mxe=1e6+10;
const int mod=1e9+7;
string s;
int n;
string sub_str(int l,int r){return s.substr(l,r-l+1);
}
void solve(){cin>>s;n=s.size();s=" "+s;for(int i=1;i<=n;i+=2){swap(s[i],s[i+1]);}cout<>__;while(__--)solve();return 0;
}

B - Call the ID Number

模拟

Code：

#include 
using namespace std;
#define int long long
using i64 = long long;
const int mxn=1e6+10;
const int mxe=1e6+10;
const int mod=1e9+7;
vector v;
map mp;
int n;
int a[mxn];
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){if(!mp[i]) mp[a[i]]++;}for(int i=1;i<=n;i++){if(!mp[i]) v.push_back(i);}cout<>__;while(__--)solve();return 0;
}

C - Make Takahashi Happy

DFS

思路：

直接暴力DFS

Code：

#include 
using namespace std;
#define int long long
using i64 = long long;
const int mxn=1e2+10;
const int mxe=1e6+10;
const int mod=1e9+7;
map mp;
int n,m,ans;
int a[mxn][mxn];
int dx[2]={1,0},dy[2]={0,1};
int vis[mxn][mxn];
bool check(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;
}
void dfs(int x,int y){if(x==n&&y==m){ans++;return;}for(int i=0;i<2;i++){int vx=x+dx[i],vy=y+dy[i];if(check(vx,vy)&&!vis[vx][vy]&&mp[a[vx][vy]]==0){vis[vx][vy]=1;mp[a[vx][vy]]=1;dfs(vx,vy);mp[a[vx][vy]]=0;vis[vx][vy]=0;}}
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) cin>>a[i][j];}vis[1][1]=1;mp[a[1][1]]=1;dfs(1,1);cout<>__;while(__--)solve();return 0;
}

D - Tying Rope

并查集判环

题意：

有n条绳子，将一些绳子的头尾连接，问你最后有多少环和多少链

思路：

经典并查集判环

Code：

#include 
using namespace std;
#define int long long
using i64 = long long;
const int mxn=2e5+10;
const int mxe=1e6+10;
const int mod=1e9+7;
string p1,p2;
int n,m,u,v,x,y,cnt;
int f[mxn];
int find(int x){return f[x]=(x==f[x])?x:find(f[x]);
}
void join(int u,int v){int f1=find(u),f2=find(v);if(f1!=f2) f[f1]=f2;
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){cin>>u>>p1>>v>>p2;if(find(u)==find(v)) x++;join(u,v);}for(int i=1;i<=n;i++){if(f[i]==i) cnt++;}cout<>__;while(__--)solve();return 0;
}

E - Geometric Progression

分治+等比数列求和

思路：

Code：

#include 
using namespace std;
#define int long long
using i64 = long long;
const int mxn=2e5+10;
const int mxe=1e6+10;
const int mod=1e9+7;
int a,x,m;
int ksm(int a,int b,int mod){int res=1;while(b>0){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;
}
int sum(int x){if(x==1) return 1;if(x%2==0) return ((1+ksm(a,x/2,m))*sum(x/2)%m)%m;return (1+a*sum(x-1))%m;
}
void solve(){cin>>a>>x>>m;cout<>__;while(__--)solve();return 0;
}

F - Zero or One

枚举+二分

思路：

对于2~1000进制，直接去暴力check

对于更大的进制，更换枚举对象

去枚举01串，对于每一个01串，去二分刚好满足条件的进制，如果这个进制>1000，就加上贡献

Code：

// हर हर महादेव
using namespace std;
#include 
#define int long long intconst int lim = 1e3 + 5;
const int dig = 7;
const int N = (int) 1e18 + 50;
const int inf = (int) 1e18 + 50;bool check(int n,int b){while(n){if(abs(n % b) > 1){return false;}n /= b;}return true;
}int interpret_in_base_b(int mask,int b){int ans = 0;__int128 pw = 1;bool flag = false;for(int i = 0; i < dig; i++){if(1 << i & mask){if(flag){return inf;}ans += pw;}pw *= b;if(pw > N){flag = true;}}return ans;
}int binary_search_base(int n,int mask){ // value of b for which mask interpreted in base b is equal to n. Returns -1 if there is no such bint l = 0,r = N,ans = -1;while(l <= r){int m = (l + r) >> 1;if(interpret_in_base_b(mask,m) <= n){ans = m;l = m + 1;}else{r = m - 1;}}return interpret_in_base_b(mask,ans) == n ? ans : -1;
}void testcase(){int n; cin >> n;// checking for b in [2,1000)int ans = 0;for(int i = 2; i < lim; i++){ans += check(n,i);}// bitmasking + binary searchfor(int mask = 1;mask < (1 << dig);mask++){int here = binary_search_base(n,mask);if(here >= lim){ans++;}}cout << ans << '\n';
}int32_t main(){ios::sync_with_stdio(false);cin.tie(0);int tt; cin >> tt;while(tt--){testcase();}return 0;
}

G - Triple Index

莫队

思路：

第一次写莫队，有点紧张

莫队利用了分块思想，把询问离线处理，然后按块的ｌ进行排序，减少指针移动次数

唯一要改的就是add和del函数

具体看代码：

#include 
using namespace std;
#define int long long
const int mxn=2e5+10;
int n,m,sq,l=1,r=0,cur;
int a[mxn],cnt[mxn],ans[mxn],block[mxn];
struct Query{int l,r,id;
}Q[mxn];
bool cmp(Query a,Query b){if(block[a.l]!=block[b.l]) return a.lb.r;
}
int C3(int x){return x*(x-1)*(x-2)/6;
}
void add(int p){cur-=C3(cnt[a[p]]);cnt[a[p]]++;cur+=C3(cnt[a[p]]);
}
void del(int p){cur-=C3(cnt[a[p]]);cnt[a[p]]--;cur+=C3(cnt[a[p]]);
}
void solve(){cin>>n>>m;sq=ceil(1.*n/sqrt(m));for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){cin>>Q[i].l>>Q[i].r;Q[i].id=i;block[i]=(i-1)/sq+1;}sort(Q+1,Q+1+m,cmp);l=1,r=0;for(int i=1;i<=m;i++){while(l>Q[i].l) add(--l);while(rQ[i].r) del(r--);ans[Q[i].id]=cur;}for(int i=1;i<=m;i++) cout<>__;while(__--)solve();return 0;
}