北市學科能力競賽
from Yui Huang
2169 . 出戰排序 (Arrangement)
約瑟夫問題
#include <bits/stdc++.h>
using namespace std;
int f(int n, int m) {
int pos = 0;
for (int i = 2; i <= n; i++) {
pos = (pos + m) % i;
}
return pos + 1;
}
int main() {
int n, k;
cin >> n >> k;
for (int m = 2; m <= 30000; m++) {
if (f(n, m) == k) {
cout << m << endl;
return 0;
}
}
cout << 0 << endl;
return 0;
}
2170 . 地圖編修 (Map)
題解
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n"
#define nnn " "
#define nnnn "\n----------------------\n"
#define N 105
int n,mod;
int v[N][N];
int fpow(int x,int y){
if(!y)return 1;
if(y&1)return fpow(x,y-1)*x%mod;
int z=fpow(x,y/2)%mod;
return z*z%mod;
}
void out(){
cout<<nnnn;
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
cout<<v[i][j]<<nnn;
}
cout<<nn;
}
cout<<nnnn;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
//istringstream cin("3 101 \
69 59 89 \
5 4 2 \
3 6 7 \
2 0 1");
cin>>n>>mod;
for(int i=1;i<=n+1;i++){//存入陣列
for(int j=1;j<=n;j++){
cin>>v[j][n-i+2];
}
}
for(int i=1;i<=n;i++){
//例外狀況交換(目標為0)
if(v[i][i]==0){
for(int j=i;j<=n;j++){//往後找不是0的
if(v[j][i]!=0){//找到不是0的
for(int k=1;k<=n+1;k++){//交換
swap(v[i][k],v[j][k]);
}
break;
}
}
}
//第i個變成1
int e=fpow(v[i][i],mod-2);
for(int j=i;j<=n+1;j++){//前面都是0了，往後乘模逆元就好
v[i][j]=v[i][j]*e%mod;
}
//其他變成0
for(int j=1;j<=n;j++){
if(j==i)continue;//跳過自己
int tmp=v[j][i];//要先存起來不然會被改掉
for(int k=i;k<=n+1;k++){
v[j][k]= ((v[j][k] - (v[i][k]*tmp))%mod+mod)%mod;
}
}
}
for(int i=n;i>=1;i--)cout<<v[i][n+1]<<" ";
}
2171 . 打卡遊戲 (Checkin)
#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define nnn " "
#define N 2000
// #define int long long
int n,m,x,y,z,k;
vector<int>v[N];
bool vis[N];
int odd=0;
void dfs(int f){
vis[f]=true;
if(v[f].size()&1){
odd++;
}
for(int i:v[f]){
if(!vis[i]){
dfs(i);
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
//istringstream cin("3 3 100 20 5 \
1 1 5 \
1 2 4 \
3 3 8 \
2 1 4 \
2 2 4");
cin>>n>>m>>x>>x>>k;
for(int i=0;i<k;i++){
cin>>x>>y>>z;
v[x].push_back(y+n);
v[y+n].push_back(x);
}
int ans=0;
for(int i=1;i<=n+m;i++){
if(!vis[i] && v[i].size()){
odd=0;
dfs(i);
ans+=max( odd/2 , 1);
}
}
cout<<ans;
}
2172 . 物種演化 (Evolution)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200000
#define nn "\n"
int n,m;
vector<int>v[N];
bool vis[N];
int tin[N],tout[N],d[N],t=0,lgn;
vector<vector<int>> anc(N,vector<int>(17,-1));
void dfs(int f){
vis[f]=true;
t++;
tin[f]=t;
for(int i:v[f]){
if(!vis[i]){
anc[i][0]=f;
for(int j=1;j<=lgn;j++){
if(anc[i][j-1]==-1)break;
anc[i][j]=anc[anc[i][j-1]][j-1];
}
d[i]=d[f]+1;
dfs(i);
}
}
t++;
tout[f]=t;
}
int isanc(int a,int b){
return tin[a]<=tin[b] && tout[a]>=tout[b];
}
int lca(int a,int b){
if(isanc(a,b))return a;
if(isanc(b,a))return b;
for(int j=lgn;j>=0;j--){
if(anc[a][j]!=-1 && !isanc(anc[a][j],b)){;
a=anc[a][j];
}
}
return anc[a][0];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
//istringstream cin("10 5 \
2 9 \
3 9 \
7 9 \
8 5 \
9 5 \
6 1 \
0 1 \
5 4 \
1 4 \
2 3 \
8 6 \
1 7 \
9 5 \
5 0");
cin>>n>>m;
lgn=__lg(n);
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(0);
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
int z=lca(x,y);
cout<< d[x]-d[z]+d[y]-d[z]<<nn;
}
}