Codeforces 989 P循环节01构造 ABCD连通块构造 思维对云遮月参考系坐标轴转换
2024-10-05 09:37:13
A
直接判存不存在连续的三个包含A,B,C就行
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 1e5 + , MAXM = 1e5 + , N = 2e5 + ;
const int MAXQ = ;
int sum[];
char f[];
int main()
{
ios_base::sync_with_stdio();
cin.tie(); string a;
cin >> a;
int len=a.size();
for (int i = ; i < a.size(); i++)
{
int l = max(i - , );
int r = min(len - , i + );
if (a[i] == 'A')
{
for (int j = l; j <= r; j++)
{
sum[j] += ;
}
}
else if (a[i] == 'B')
{
for (int j = l; j <= r; j++)
{
sum[j] += ;
}
}
else if (a[i] == 'C')
{
for (int j = l; j <= r; j++)
{
sum[j] += ;
}
}
}
for (int i = ; i < a.size(); i++)
{
if (sum[i] == )
{
cout << "Yes" << endl;
return ;
}
}
cout << "No" << endl;
return ;
}
B
下列情况有答案
1.f[i]!=f[i-p]
2.f[i]=f[i-p]='.'
3.f[i]!='.'&&f[i-p]='.'或者f[i]='.'&&f[i-p]!='.'
不是这几种情况直接输出NO即可 是的话 先构造出一处然后剩下的随便赋值了
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 1e5 + , MAXM = 1e5 + , N = 2e5 + ;
const int MAXQ = ;
int sum[];
char f[];
int main()
{
ios_base::sync_with_stdio();
cin.tie(); int flag = ;
int n, p;
scanf("%d %d", &n, &p);
scanf("%s", f + );
for (int i = p + ; i <= n; i++)
{
if (f[i] == '.')
{
if (f[i - p] != '.')
{
if (f[i - p] == '')
{
f[i] = '';
}
else
{
f[i] = '';
}
flag = ;
}
else
{
f[i] = '';
f[i - p] = '';
flag = ;
}
}
else
{
if (f[i - p] == '.')
{
if (f[i] == '')
{
f[i - p] = '';
}
else
{
f[i - p] = '';
}
flag = ;
}
else
{
if (f[i] != f[i - p])
{
flag = ;
}
}
}
}
for (int i = ; i <= n; i++)
{
if (f[i] == '.')
{
f[i] = '';
}
}
if (!flag)
{
cout << "No" << endl;
}
else
{
printf("%s\n", f + );
}
}
C
构造题
直接搞个48*50的大块 分成4个12*50的小块
再满足条件地在大块里面扣一个个1*1的小块即可
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 1e5 + , MAXM = 1e5 + , N = 2e5 + ;
const int MAXQ = ;
int sum[];
char f[][];
int main()
{
ios_base::sync_with_stdio();
cin.tie(); int a, b, c, d;
cin >> a >> b >> c >> d;
cout << << " " << << endl;
for (int i = ; i <= ; i++)
{
for (int j = ; j <= ; j++)
{
if (i <= )
{
f[i][j] = 'A';
}
else if (i <= )
{
f[i][j] = 'B';
}
else if (i <= )
{
f[i][j] = 'C';
}
else
{
f[i][j] = 'D';
}
}
}
a--, b--, c--, d--;
int dx = , dy = ;
for (int i = ; i <= a; i++)
{
if (dy > )
{
dy -= , dx += ;
}
f[dx][dy] = 'A';
dy+=;
}
dx=,dy=;
for (int i = ; i <= b; i++)
{
if (dy > )
{
dy -= , dx += ;
}
f[dx][dy] = 'B';
dy+=;
}
dx=,dy=;
for (int i = ; i <= c; i++)
{
if (dy > )
{
dy -= , dx += ;
}
f[dx][dy] = 'C';
dy+=;
}
dx=,dy=;
for (int i = ; i <= d; i++)
{
if (dy > )
{
dy -= , dx += ;
}
f[dx][dy] = 'D';
dy+=;
}
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
cout<<f[i][j];
}
cout<<endl;
}
}
D
题意:
给你n块云(1<=n<=1e5) 每块云的长度是确定的L 月亮在原点 每块云覆盖的区间为[Xi,Xi+L](-1e8<=Xi<=1e8) 初始每块云的速度是1或者-1
现在给你一个Wmax 你可以选择一个速度W(-Wmax<=W<=Wmax)使得有一对云在某一个时间同时覆盖住月亮
问你可以由多少对
解:
http://codeforces.com/blog/entry/59968
把X轴上再加一条Y轴表示时间 这样某一块云运动的轨迹就变成了一个斜着的条
如果两个云有交集的话 在图上就变成有一个公共的小蓝方块
接着我们把W的速度转给月亮 而不是给云 这样云的速度就不变 方便思考和计算
如果一对云可以同时遮到月亮的话 小蓝方块与黄色月亮运动范围是有交集的 即小蓝方块的最高点Y坐标大于下界斜率*当前横坐标
因为1<=W<=Wmax 所以月亮下界的斜率最小为1/Wmax 假设有一个往左的云u 有一个往右的云v 可以算出他们的小蓝块的最高点坐标为((Xu+Xv+L)/2,(Xu-Xv+L)/2)
接下来的要求即是解不等式
把Xu+Xv+L分>=0与<0两种情况讨论即可
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 1e5 + , MAXM = 1e5 + , N = 2e5 + ;
const int MAXQ = ;
int n, l, w;
int x[MAXN], v[MAXN];
vector<int> pos, neg;
inline int div_floor(ll a, int b)
{
if (b == )
{
if (a > )
{
return INT_MAX;
}
else
{
return INT_MAX * -;
}
}
if (a % b < )
{
a -= (b + a % b);
}
return a / b;
}
int main()
{
scanf("%d %d %d", &n, &l, &w);
for (int i = ; i < n; i++)
{
scanf("%d %d", &x[i], &v[i]);
if (v[i] == )
{
pos.push_back(x[i]);
}
else
{
neg.push_back(x[i]);
}
}
sort(pos.begin(), pos.end()), sort(neg.begin(), neg.end());
ll anser = ;
for (int v : neg)
{
auto barrier = lower_bound(pos.begin(), pos.end(), -v - l);
int ansmax0 = div_floor(1LL * (v + l) * (w + ) - , w - );
int ansmax1 = div_floor(1LL * (v + l) * (w - ) - , w + );
anser += (upper_bound(pos.begin(), barrier, ansmax0) - pos.begin()) + (upper_bound(barrier, pos.end(), min(v, ansmax1)) - barrier);
}
printf("%lld\n", anser);
}
E
待补
最新文章
- 关于jqGrig如何写自定义格式化函数将JSON数据的字符串转换为表格各个列的值
- c# 集合
- Linux 各目录的作用
- Oracle创建删除用户,角色,表空间,导入导出数据库命令总结(转载)
- 学习笔记 之--AJAX核心对象 XMLHttpRequest
- [Mugeda HTML5技术教程之17] 理解Mugeda访问统计结果
- 什么是比特币（Bitcoin）?
- dtree实现上下级关系的显示
- PPT素才搜索简谈
- 用Python写WebService接口并且调用
- 最短路径（Dijkstra算法)
- Maya cmds pymel 获取安装选择顺序选择的物体
- 性能优化-YAHOO军规
- OpenGL 获取当前屏幕坐标的三维坐标（gluUnProject使用例子 VS+glut）
- centos更换yum源为aliyun源
- systemd-analyze – 在Linux中查找系统启动性能统计信息
- sql 计算两个经纬度点之间的距离
- L1-032 Left-pad
- hdu 1028 整数划分 （母函数）
- Linux系统——Ansible批量管理工具