10.18 J 组模拟赛*2
上午 “J”组模拟赛
T1:一维围棋
题面
赛时：100
很简单的一道入门题，注意特判
int n;
char a[105];
void init()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int mx = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == '.')
{
int lb = 0, rb = 0;
for (int j = i - 1; j >= 1; j--)
{
if (a[j] == 'W' && j != 1)
continue;
if (a[j] == '.')
break;
lb = 1;
break;
}
for (int j = i + 1; j <= n; j++)
{
if (a[j] == 'W' && j != n)
continue;
if (a[j] == '.')
break;
rb = 1;
break;
}
if (lb && rb)
{
continue;
}
lb = 0, rb = 0;
for (int j = i - 1; j >= 1; j--)
{
// cout << a[j] << ' ';
if (a[j] == 'W')
{
break;
}
if (a[j] == '.')
{
lb = 0;
break;
}
lb++;
if (j == 1)
lb = 0;
// break;
}
// cout << endl;
for (int j = i + 1; j <= n; j++)
{
// cout << a[j] << ' ';
if (a[j] == 'W')
{
break;
}
if (a[j] == '.')
{
rb = 0;
break;
}
rb++;
if (j == n)
rb = 0;
}
// cout << endl;
// cout << i << ' ' << lb << ' ' << rb << '\n';
mx = max(mx, max(lb, rb));
}
}
cout << mx;
}
T2 斜二等轴测图
题面
赛时：100
画图题，注意斜线的判定，当一个点‘.’的右上角与左下角为+，四周之多有两个‘-’‘|’时，这个格子为斜杠。
bool check(int x, int y)
{
int cnt = 0;
if (a[x][y - 1] != '.')
cnt++;
if (a[x][y + 1] != '.')
cnt++;
if (a[x - 1][y] != '.')
cnt++;
if (a[x + 1][y] != '.')
cnt++;
if (cnt > 2)
return 0;
return 1;
}
void init()
{
memset(a, '.', sizeof(a));
cin >> x >> y >> z;
for (int i = 1; i <= y + y + z + z + 1; i += 2)
{
for (int j = max(1ll, (y + 1 - i / 2 - 1) * 2 + 1), k = 1; k <= x; k++, j += 2)
{
a[i][j] = '+';
a[i][j + 1] = '-';
}
a[i][max(1ll, (y + 1 - i / 2 - 1) * 2 + 1) + x * 2] = '+';
}
for (int i = 1; i <= y + y + x + x + 1; i += 2)
{
for (int j = min(y + y + z + z + 1, (x + 1 - i / 2 - 1) * 2 + y + y + z + z + 1), k = 1; k <= z; k++, j -= 2)
{
a[j][i] = '+';
a[j - 1][i] = '|';
}
a[min(y + y + z + z + 1, (x + 1 - i / 2 - 1) * 2 + y + y + z + z + 1) - z * 2][i] = '+';
}
for (int i = 1; i <= z + z + y + y; i++)
for (int j = 1; j <= y + y + x + x + 1; j++)
{
if (a[i - 1][j + 1] == '+' && a[i + 1][j - 1] == '+' && check(i, j))
{
a[i][j] = '/';
}
}
// cout << x << ' ' << y << ' ' << endl;
for (int i = 1; i <= z + z + y + y + 1; i++)
{
for (int j = 1; j <= y + y + x + x + 1; j++)
{
// cout << i << ' ' << j << ' ';
cout << a[i][j];
}
cout << endl;
}
}
T3 炸弹
题面
赛时：44pts
44pts:
暴力建图，如果炸弹i能炸到炸弹j时，建单向边。然后暴力爬每一个点有几个可达点，时间复杂度\(O(n^2)\)
int n;
vector<int> a[1005];
int x[1005], r[1005];
bool v[1005];
int dfs(int x)
{
v[x] = 1;
int cnt = 1;
for (int i = 0; i < a[x].size(); i++)
{
int y = a[x][i];
if (v[y])
continue;
v[y] = 1;
cnt += dfs(y);
}
return cnt;
}
void init()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i] >> r[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
continue;
if (abs(x[i] - x[j]) <= r[i])
{
a[i].push_back(j);
}
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
memset(v, 0, sizeof(v));
cnt = (cnt + dfs(i) * i) % 1000000007;
}
cout << cnt;
}
100pts
coding...
T4 冲塔
题面
赛时：0pts
16pts
暴力dfs这个塔推不推
100pts
coding...
下午 J组模拟赛
T1 星空
【问题描述】
点点星空是一张n×m的棋盘，左下角有颗星星。尤和千每次可以将星星向右边、右上、上边移动一格。先把星星移动到右上角的人胜利，尤和千轮流移动，尤先手，问尤是否必胜？
【输入格式】
从文件 star.in 中读入数据
多组数据，每行两个整数n,m，当 n=m=0 时数据停止。
【输出格式】
输出到文件 star.out 中。
对于每组数据，如果尤必胜输出“Yuri” ，否则输出“Chito”。
赛时：0pts
很简单的入门题，博弈论，但我结论推错了
我们假设现在的情况是我们走完了
如果我们此时停留在红色点就赢了。
停留在绿色点就必输。
所以如果n,m皆为奇数时必胜。
#include<bits/stdc++.h>
using namespace std;
int x,y;
int main(){
// freopen("star.in","r",stdin);
// freopen("star.out","w",stdout);
while(cin>>x>>y){
if(x==y&&y==0) break;
if(y%2==1&&x%2==1){
cout<<"Chito\n";
}
else cout<<"Yuri\n";
}
}
T2 少女
【问题描述】
少女在图上开车，她们希望把图上每条边分配给与其相连的点中的一个，并且每个点最多被分配一条边，问可能的方案数？
【输入格式】
从文件 girl.in 中读入数据
第一行两个整数 N,M代表点数和边。
接下来M行每两个整数代表一条边。
【输出格式】
输出到文件 girl.out 中。
一行个整数代表答案对 10^9+7取模之后的值。
赛时：0pts
并查集一道，注意最后的统计方案
int n,fa[200005],cnt[200005];
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void init() {
cin>>n;
for(int i=1;i<=2*n;i++){
fa[i]=i;
cnt[i]=1;
}
int m;
cin>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
// if(x==y) x+=n;
int fx=find(x),fy=find(y);
// cout<<fx<<' '<<fy<<endl;
if(fx==fy) cnt[fx]=2;
else fa[fx]=fy,cnt[fy]+=cnt[fx];
}
int he=1;
for(int i=1;i<=n;i++){
if(find(i)==i) he=(he*cnt[i])%((int)1e9+7);
}
cout<<he;
}
T3 数组异或
题面
50pts
暴力\(n^4\),注意取模
100pts
我们可以把每一位（2进制）上0/1的个数统计出来（a,b都需要统计），然后按照异或的模式统计即可。
#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],b[100005],ac[32][2],bc[32][2],c[100005];
void cb(int x){
for(int i=0;i<31;i++){
ac[i][a[x]%2]+=1;
bc[i][b[x]%2]+=1;
// bc[i][b[x]%2]%=2;
a[x]/=2;
b[x]/=2;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
for(int i=1;i<=n;i++){
cb(i);
for(int j=30;j>=0;j--){
long long tmp=ac[j][0]*bc[j][1]+ac[j][1]*bc[j][0];
tmp%=((int)1e9+7);
tmp=tmp*(1<<j)%((int)1e9+7);
c[i]=(c[i]+tmp)%((int)1e9+7);
}
}
for(int i=1;i<=n;i++){
cout<<c[i]<<" ";
}
return 0;
}
T4 下棋
【问题描述】
n+e 很会下象棋。
他厌烦了8行8列的固定棋盘，就开始思考这样的问题：
在一个n行m列的棋盘上，放置很多的炮(也可以一个也不放)，使得没有一个炮可以攻击到另一个炮，有多少种放置方法？
答案可能很大，请你将答案对9999973取模。
炮的攻击方式是越过同一行或同一列的一个棋子打到后面的下一个棋子。
n+e很强，他3秒钟就想出了做法。现在，他把这题给了你，请你解决它吧。
【输入格式】
从文件 chess.in 中读入数据
一行两个整数n,m,表示行和列。
【输出格式】
输出到文件 chess.out 中。
一个整数，表示方案数对9999973取模的结果。
100pts
很明显，一行/列最多放2个炮。
我们定义\(f_{i,j,k}\)为：处理完第\(i\)行，前\(i\)行有\(j\)行没有炮，\(k\)行有一个炮。很明显一行放两个炮的行数是可以算出来的。
一共有六种情况
- 不放
- 一个炮，放在原来没炮的某一列上
- 一个炮，放在原来有一个炮的某一列上
- 两个炮，一个在原来没炮的列上，一个在原来一个炮的列上
- 两个炮，都放在原来没炮的列上
- 两个炮，都放在原来一个炮的列上
如果第 i 行放了 0 个，那么 \(f_{i,j,k}\) 可以从 \(f_{i-1,j,k}\)转移而来。
如果第 i 行放了 1 个，那么\(f_{i,j,k}\) 可以从 \(f_{i-1,j+1,k-1}\)或者
\(f_{i-1,j-1,k}\) 转移而来。
如果第 i 行放了 2 个，那么 \(f_{i,j,k}\) 可以从 \(f_{i-1,j,k-1}\) 或者
\(f_{i-1,j-2,k}\) 或者 \(f_{i-1,j+2,k-2}\) 转移而来。
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long dp[105][105][105];
int calc(int x) {
return (x*(x-1))/2;
}
int main(){
cin>>n>>m;
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=m-j;k++){
dp[i][j][k]=dp[i-1][j][k];
if(j)dp[i][j][k]+=dp[i-1][j-1][k]*(m-k-j+1);
if (j<m&&k)dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1);
if (j&&k)dp[i][j][k]+=dp[i-1][j][k-1]*j*(m-j-k+1);
if (j>1)dp[i][j][k]+=dp[i-1][j-2][k]*calc(m-k-j+2);
if (j<=m-2&&k>1)dp[i][j][k]+=dp[i-1][j+2][k-2]*calc(j+2);
dp[i][j][k]%=((int)(9999973));
}
}
}
int cnt=0;
for(int i=0;i<=m;i++){
for(int j=0;j<=m-i;j++){
cnt+=dp[n][i][j];
cnt%=((int)(9999973));
}
}
cout<<cnt<<endl;
}