A.Bus to Udayland
题意：已知一辆公交车，有些座位已经有人(X),现在两个人要上车，要求坐在同一排而且相邻
SB模拟
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
int n;
char a[1005][8];
bool z=0;
cin>>n;
int m,x,y;
for(int i=0;i<n;i++){
for(int j=0;j<5;j++)
cin>>a[i][j];
if((a[i][0]=='O'&&a[i][1]=='O')){
z=1;
m=i;x=0;
y=1;
}
if((a[i][3]=='O'&&a[i][4]=='O'))
{
z=1;
m=i;x=3;
y=4;
}
}
if(z){
a[m][x]='+';
a[m][y]='+';
cout<<"YES"<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<5;j++)
cout<<a[i][j];
cout<<endl;
}
}
else cout<<"NO"<<endl;
}
B.Chris and Magic Square
题意：已知一个方阵有且仅有一个元素为0，问你能否将这个0改为一个数，使得该方阵每一行，每一列，两条对角线上的元素和都相等，不存在输出-1，注意方阵为1*1时随便输出一个值
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
long long int a[505][505],b[505]={0},c[505]={0},p=0,q=0,v=0;
int n;
cin>>n;
int x,y;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
b[i]+=a[i][j];
if(a[i][j]==0){
x=i;
y=j;
}
if(i==j)
p+=a[i][j];
if(i+j==n-1)
q+=a[i][j];
}
}
for(int j=0;j<n;j++)
for(int i=0;i<n;i++)
c[j]+=a[i][j];
sort(b,b+n);
sort(c,c+n);
if(n==1){
cout<<1<<endl;
return 0;
}
if(x!=y&&(y+x)!=n-1){
if(c[n-1]==c[1]&&c[0]==b[0]&&b[n-1]==b[1]&&b[1]==c[1]&&c[1]==p&&p==q&&c[n-1]-c[0]>0)
cout<<c[n-1]-c[0]<<endl;
else cout<<-1<<endl;
}
else if((x+y)==n-1&&x==y){
if(c[n-1]==c[1]&&c[0]==b[0]&&b[n-1]==b[1]&&b[1]==c[1]&&p==q&&c[0]==q&&c[n-1]-c[0]>0)
cout<<c[n-1]-c[0]<<endl;
else cout<<-1<<endl;
return 0;
}
else if(x==y){
if(c[n-1]==c[1]&&c[0]==b[0]&&b[n-1]==b[1]&&b[1]==c[1]&&c[1]==q&&c[0]==p&&c[n-1]-c[0]>0)
cout<<c[n-1]-c[0]<<endl;
else cout<<-1<<endl;
return 0;
}
else if((x+y)==n-1){
if(c[n-1]==c[1]&&c[0]==b[0]&&b[n-1]==b[1]&&b[1]==c[1]&&c[1]==p&&c[0]==q&&c[n-1]-c[0]>0)
cout<<c[n-1]-c[0]<<endl;
else cout<<-1<<endl;
}
}
C.Coloring Trees
题意：已知n棵树排成一排，和m种颜色1,2,3,4,,,m，每个树有一个值c[i]，表示树被染成的颜色，0表示没有染上颜色，现在需要将没有染色的树染上色，将第i(1<=i<=n)棵树染成第j(1<=j<=m)种颜色需要花费pi，定义树染色后的序列美丽度为颜色连续相同的组数，例2, 1, 1, 1, 3, 2, 2, 3, 1, 3 美丽度为 7 ：{2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}.问你使得树的美丽度为k的最小花费 1<=k<=n<=100 m<=100，dp的思想很明显，dp[i][j][q]表示第i棵树选择第j种颜色时前i棵树美丽度为q时的最小花费，由于美丽度是否增加和前一棵树有关故，枚举前一棵树的颜色，很好转移复杂度$O(nm^2k)$
注意会爆int
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define minn(a,b) a<b? a:b
using namespace std;
const int maxn=105;
typedef long long ll;
const ll INF=1e13;
ll dp[maxn][maxn][maxn];
int a[maxn],c[maxn][maxn];
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=q;k++)
dp[i][j][k]=INF;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&c[i][j]);
for(int j=0;j<=m;j++)
dp[0][j][0]=0;
if(a[1]==0){
for(int i=1;i<=m;i++)
dp[1][i][1]=c[1][i];
}
else dp[1][a[1]][1]=0;
for(int i=1;i<=n;i++)
for(int k=1;k<=q;k++)
for(int j=1;j<=m;j++){
if(a[i]!=0){
dp[i][a[i]][k]=minn(dp[i-1][a[i]][k],dp[i][a[i]][k]);
for(int p=1;p<=m;p++)
if(a[i]!=p)
dp[i][a[i]][k]=minn(dp[i][a[i]][k],dp[i-1][p][k-1]);
break;
}
else{
dp[i][j][k]=minn(dp[i][j][k],dp[i-1][j][k]+c[i][j]);
for(int p=1;p<=m;p++)
if(p!=j||i==1){
dp[i][j][k]=minn(dp[i][j][k],dp[i-1][p][k-1]+c[i][j]);
}
}
}
long long ans=INF;
for(int j=1;j<=m;j++)
ans=minn(ans,dp[n][j][q]);
if(ans!=INF)
printf("%lld
",ans);
else printf("-1
");
}
D. Directed Roads
题意：已知n个小镇编号为1,2,3,,,n,每个小镇向其他小镇连了一条有向边，现在你可以随便改变这些边的方向，使得任意两个小镇不能相互到达，题目给出的连法也算在内。
初始ans=1，首先将有向图变为无向图，要找到所有的环，则环内点相互到达只有两种途径，要么顺时针，要么逆时针，设环内的点为x，则$ans=ans(2^x-2)$,对于所有不在环内的点，它的边无论怎么改变都都符合要求，设环外点数为y，则$ans=ans2^y$;
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
#define minn(a,b) a<b? a:b
using namespace std;
typedef long long ll;
const ll M=1e9+7;
const int maxn=2e5+5;
struct Edge
{
int u,v;
Edge(int u,int v):u(u),v(v){}
};
int vis[maxn],pre[maxn],iscut[maxn],bccno[maxn];
int dfs_clock,bcc_cnt;
vector<int> g[maxn],bcc[maxn];
stack<Edge> s;
int dfs(int u,int fa){
int lowu=pre[u]=++dfs_clock;
int child=0;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
Edge e=(Edge){u,v};
if(!pre[v]){
s.push(e);
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>=pre[u]){
iscut[u]=true;
bcc_cnt++;
bcc[bcc_cnt].clear();
for(;;){
Edge x=s.top();s.pop();
if(bccno[x.u]!=bcc_cnt){bcc[bcc_cnt].push_back(x.u);bccno[x.u]=bcc_cnt;}
if(bccno[x.v]!=bcc_cnt){bcc[bcc_cnt].push_back(x.v);bccno[x.v]=bcc_cnt;}
if(x.u==u&&x.v==v) break;
}
}
}
else if(pre[v]<pre[u]&&v!=fa){
s.push(e);
lowu=min(lowu,pre[v]);
}
}
if(fa<0&&child==1) iscut[u]=0;
return lowu;
}
void find_bcc(int n){
memset(pre,0,sizeof(pre));
memset(iscut,0,sizeof(iscut));
memset(bccno,0,sizeof(bccno));
dfs_clock=bcc_cnt=0;
for(int i=1;i<=n;i++)
if(!pre[i])
dfs(i,-1);
}
ll powmod(int a,int n){
if(n==0)
return 1;
ll x=powmod(a,n/2);
ll ans=x*x%M;
if(n%2==1) ans=ans*a%M;
return ans;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
g[i].push_back(x);
g[x].push_back(i);
}
find_bcc(n);
ll ans=1;
int sum=n;
for(int i=1;i<=bcc_cnt;i++){
sum-=bcc[i].size();
ans=(ans*(powmod(2,bcc[i].size())-2))%M;
}
ans=(ans*powmod(2,sum))%M;
printf("%lld
",ans);
}
E. ZS and The Birthday Paradox
题意：在某个岛上一年有$2^n$天($1<=n<=10^{18}$),有k个人($2<=k<=10^{18}$)，问你这k个人中至少有两个人同一天生日的概率是多大，答案将分数先化为最简分数再对$M=10^6+3$取模
首先，如果人数大于天数，则概率为1
根据概率公式，至少两人同一天生日的概率为：$egin{align} P &=1- frac{2^n(2^n-1)...*(2^n-(k-1))}{(2^n)^k} end{align} $
首先对分子分母化简，应当同时除以$2^{n+sum_{i=1}^{k-1} i/2}$
由于最后的结果要对M取模，分子为连续k个整数，分母只有2的倍数，分子分母只同时除以2的倍数，考虑到M为质数，故当k>=M时，这连续k个数中一定有M的倍数，此时化简后同时对M取模，则分子取模后为0，此时分子分母均为$2^{n*k-(n+sum_{i=1}^{k-1} i/2)}$，使用快速幂即可。
当k<M时，k范围较小，则直接暴力计算即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
#define minn(a,b) a<b? a:b
using namespace std;
typedef long long ll;
const ll M=1e6+3;
ll n,k;
ll powmod(int a,ll n){
if(n==0)
return 1;
ll x=powmod(a,n/2);
ll ans=x*x%M;
if(n%2==1) ans=ans*a%M;
return ans;
}
int main(){
scanf("%lld%lld",&n,&k);
ll z=1;
for(int i=1;i<=n;i++){
z=z*2;
if(z>k)
break;
}
if(z<k){
printf("1 1
");
return 0;
}
ll q=k-1;
ll sum2=0;
ll m=M-1;
while(q>0){
sum2+=q/2;
q=q/2;
}
ll x=(n%m*((k-1)%m)%m-sum2%m+m)%m;
ll y=powmod(2,x);
if(k-1>=M){
printf("%lld %lld
",y,y)
return 0;
}
else {
ll ans=1;
for(int i=1;i<=k-1;i++){
ll p=n;
int j=i;
while(j%2==0){
j=j/2;
p--;
}
ans=ans*(powmod(2,p)-j)%M;
}
printf("%lld %lld
",(y-ans+M)%M,y);
}
}