One and Two
算法本质
模拟
题目大意
给一个有1 2组成的数组a[]，是否存在一个k，使得前k个元素的连乘等于后n-k个数的连乘。
思路推演
略。
B.Sum of Two Numbers
算法本质
模拟
题目大意
给定数字n，找出一对数字a b满足：
- a+b == n
- a所有位数字和 与 b所有位数字和 差值<=1
思路推演
按位平分。
C.Matching Numbers
算法本质
思维
题目大意
给定数字n，构造一个2n的排列，要求满足：
- 每2个相邻元素组成一对（
a[2k]和a[2k+1]），a[2k]+a[2k+1] + 1 == a[2k+2]+a[2k+3]（靠左对+1 == 靠右对）
无法完成输出No。
思路推演
很容易可以求到元素总和：(1+2n)*2n/2
然后要化成n个自然数相加：(3n+3)/2 ~ (5n+1)/2
当n为奇数的时候当然不可行。
此时就要找方法看怎么填了，手动模拟一下即可得到。
D.Moving Dots
算法本质
思维
题目大意
在一条线上，有n个给定的点（不相重），任选>=2个点，玩游戏将得分加入ans，输出所有情况都玩过后的ans%mod值。
游戏内容如下：
游戏开始后，点会找最近的点（优先左边）以固定相等的速度移动，当点第一次发生碰撞后就会停下（但是任然算作点，可以被其他移动的点碰撞）。
当所有的点停下后，所有点所处不同位置数目就是分数。
n <= 3e3
点坐标：[1, 1e9]思路推演
所有情况一共n**2种，显然，此题是需要合并某个特征值，化简为n^2的复杂度。
当然，也可以考虑dp。
这其中，最合适的就是找到点 --> 贡献值。
即找到某点在不同情况下对ans的贡献值。
- 以单点来看，点会因为所选点的不同而左右移动，无法判断。
- 以dp来看，相邻的点集没有可以简算的递推公式。
- 以二分来看，并无单调性。
这其中的奥秘出在复杂度上，3e3的数据范围是支持n^2的，当然正面思考到任然有一些难度，从ans入手。
思考ans的来源，其实游戏结束后聚集在一起，可以看作最开始2个点干的，其他只是趋势。结合3e3的数据，能不能以2个点为单位，思考其对ans的贡献。
如果2点为单位，驱赶附近点，任选远处点，这2点会始终对ans有贡献。并且其他点被吸引或是自己组合与2点无关。
存在附近点的情况，可以转化为另外2点单位的情况。
复杂度允许，开整。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int x[maxn];
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>x[i];
//cal
int ans=0;
for (int i=1; i<=n; i++)
{
for (int j=i+1; j<=n; j++)
{
// debug2(i,j)
int dis=x[j]-x[i];
int l = lower_bound(x+1, x+1+n, x[i]-dis) - x; //找到第一个>=左边界的
l--; //<左边界的个数
int r = lower_bound(x+1, x+1+n, x[j]+dis) - x; //找到第一个>=右边界的
r = n - r + 1; //>=右边界的个数
ans += qpow(2, l+r, mod);
ans %= mod;
}
}
//output
cout<<ans<<endl;
return;
}
评论 (0)