【A. Bus to Udayland】http://www.codeforces.com/contest/711/problem/A
【题意】公交车上有些位置能做，有些不能坐，问是否有两个相邻的位置。
【解题方法】找到并排的2个0就行了。
【AC代码】
#include <bits/stdc++.h>
using namespace std;
int n;
char s[1010][10];
int main()
{
cin>>n;
for(int i=0; i<n; i++) cin>>s[i];
bool flag=false;
for(int i=0; i<n; i++)
{
if(s[i][0]=='O'&&s[i][1]=='O')
{
flag=true;
s[i][0]=s[i][1]='+';
break;
}
if(s[i][3]=='O'&&s[i][4]=='O')
{
flag=true;
s[i][3]=s[i][4]='+';
break;
}
}
if(flag){
puts("YES");
for(int i=0; i<n; i++)printf("%s\n",s[i]);
}
else{
puts("NO");
}
}【B. Chris and Magic Square】 http://www.codeforces.com/contest/711/problem/B
【题意】一个n*n(n<=500)的矩形中有一个格子为空，问是否能填上某个数，使得每行每列以及主对角线之后均相等。
【解题方法】n=1特判。n>=2找出某个可能合法的解，填入后再验证一下。 数据范围爆int啦。
【AC 代码】
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5+10;
LL a[550][550];
LL row[550];
LL col[550];
set<LL>s;
int c,r;
int main()
{
int n;
cin>>n;
s.clear();
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
scanf("%I64d",&a[i][j]);
if(a[i][j] == 0){
r = i,c = j;
}
}
}
if(n == 1){
printf("1\n");
return 0;
}
LL sum = 0;
for(int i = 1;i <= n;i++){
if(i != r){
for(int j = 0;j <= n;j++){
sum += a[i][j];
}
break;
}
}
for(int i = 1;i <= n;i++){
sum -= a[r][i];
}
a[r][c] = sum;
LL sum1 = 0,sum2 = 0;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
col[i] += a[i][j];
row[i] += a[j][i];
}
sum1 += a[i][i];
sum2 += a[i][n-i+1];
}
s.insert(sum1);
s.insert(sum2);
for(int i = 1;i <= n;i++){
s.insert(col[i]);
s.insert(row[i]);
}
if(s.size() > 1){
puts("-1");
}
else{
if(sum>0) cout<<sum<<endl;
else puts("-1");
}
return 0;
}【C. Coloring Trees】 http://www.codeforces.com/contest/711/problem/C
【题意】有n棵树排成一列，一共有m种颜料，有些树被涂了颜色，有些树没有。可以花费a[i][j]的代价给第i棵树涂上j的颜色。问给每棵树涂上颜色后，将树恰好分成k段的最小花费。（连续颜色相同的最长区间为一段）n,m,k<=100【解题方法】n^4的dp显而易见啦。好像有n^3的，不过n才100，谁便搞啦。
【AC 代码】O(n^4)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 1e18;
const int maxn=110;
LL a[maxn],b[maxn][maxn],dp[maxn][maxn][maxn];
int n,m,k;
int main()
{
cin>>n>>m>>k;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>b[i][j];
}
}
memset(dp,0x3f,sizeof(dp));
if(!a[1]) for(int i=1; i<=m; i++) dp[1][i][1]=b[1][i];
else dp[1][a[1]][1]=0;
for(int i=1; i<n; i++){
for(int j=1; j<=m; j++){
for(int l=1; l<=k; l++){
if(a[i+1]==0){
for(int r=1; r<=m; r++){
if(j==r) dp[i+1][r][l]=min(dp[i+1][r][l],dp[i][j][l]+b[i+1][r]);
else dp[i+1][r][l+1]=min(dp[i+1][r][l+1],dp[i][j][l]+b[i+1][r]);
}
}
else{
for(int r=1; r<=m; r++){
if(j==a[i+1]) dp[i+1][j][l]=min(dp[i+1][j][l],dp[i][j][l]);
else dp[i+1][a[i+1]][l+1]=min(dp[i+1][a[i+1]][l+1],dp[i][j][l]);
}
}
}
}
}
LL ans=inf;
for(int i=1; i<=m; i++){
ans=min(ans,dp[n][i][k]);
}
if(ans==inf) ans=-1;
printf("%I64d\n",ans);
return 0;
}【D. Directed Roads】 http://www.codeforces.com/contest/711/problem/D
【题意】有n个点，给定一个数组a[i](≠i），表示有一条i-->a[i]的有向边。可以将某些有向边的方向翻转，因此共有2^n的方案。问这些方案中有多少种方案使得所形成的图不含有环。n<=2*10^5
【解题方法】由于一共只有n条边，整个图相当于被分成了若干个联通块，且每个联通块内有且只有一个环。若某个连通块中有i个点，存在一个点数为j的环，那么其对答案的贡献为2^(i-j) * (2^j-2)
【AC 代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int maxn = 2e5+5;
int p[maxn],c[maxn],clk[maxn];
LL powmod(int x)
{
LL res=1;
while(x--)
{
res<<=1;
res%=mod;
}
return res;
}
int main()
{
int n,cnt=0;
cin>>n;
for(int i=1; i<=n; i++) cin>>p[i];
int num=n;
LL ans=1;
for(int i=1; i<=n; i++){
if(!c[i])
{
c[i]=i;
clk[i]=++cnt;
int x=i;
while(1)
{
x=p[x];
if(c[x])
{
if(c[x]==i){
int t=cnt-clk[x]+1;
ans=ans*(powmod(t)-2)%mod;
ans=ans%mod;
num-=t;
}
break;
}
else{
c[x]=i;
clk[x]=++cnt;
}
}
}
}
ans=ans*powmod(num);
ans%=mod;
if(ans<0) ans+=mod;
cout<<ans<<endl;
return 0;
}【E. ZS and The Birthday Paradox】 点击打开链接
【题意】假设一年有2^n天，问k个小朋友中有两个小朋友生日相同的概率。假设该概率约分后为 p / q ,输出p , q对1000003取模的解。n , k <= 10^18。
【解题方法】参见http://www.cnblogs.com/rpSebastian/p/5821057.html
【解题方法】若k > 2^n 则答案为1 / 1 , 否则答案为 1 - A(2^n,k) / (2^n)^k ，可以发现分子与分母的gcd必定为2^i。计算A(2^n,k)=(2^n) * (2^n-1) * ... * (2^n-k+1)含多少个因子2，相当于计算0~k-1以及2^n。求出gcd后，就可以暴力计算分子，分母对p取模后的结果，再乘上gcd的逆元。
【AC 代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e6+3;
LL powmod(LL a,LL n)
{
LL res=1;
while(n)
{
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
int main()
{
LL n,k;
scanf("%I64d%I64d",&n,&k);
if(n<=62&&k>(1LL<<n)){
printf("1 1\n");
return 0;
}
//这里想了很久啊，悲伤
LL num=0;
for(LL i=k-1; i; i>>=1){
num+=i/2;
}
//cout<<num<<endl;
LL a=powmod(2,n),b=1;
for(LL i=1; i<=k-1; i++)
{
LL temp=(a-i+mod)%mod;
b=b*temp%mod;
if(temp==0) break;
}
//cout<<b<<endl;
//cout<<a<<" "<<b<<endl;
LL inv=powmod(powmod(2,num),mod-2);
a=powmod(a,k-1);
a=a*inv%mod;
b=b*inv%mod;
b=(a-b+mod)%mod;
printf("%I64d %I64d\n",b,a);
return 0;
}
京公网安备 11010502036488号