G@rage

Description

众所周知，qm的高数总是满分。这一天数学白痴锦鱼拿着一道数学题来问qm，qm不屑做这种简单的题，于是把这道题丢给你来完成。题目是这样的：给定a、b、c三个整数，求最大的整数x，满足x^a+b*x<=c,其中x^a表示x的a次方，b*x表示b乘以x。

Input

第一行输入三个整数a(1<=a<=10),b(0<=b<=10¹⁸),c(0<=c<=10¹⁸)，分别对应题目中a、b、c三个整数。

Output

输出一个整数，表示所求的最大的x。

Sample Input

2 3 4

Sample Output

这题虽然是一道二分，但由于x^a可能过于大，所以x每次要去pow(c,1.0/a)避免爆炸。

xyjj说pow在计算longlong的时候会出现各种奇怪的问题（导致我WA了无数次），后来网上查了一下说是因为pow是计算的double所以会有精度丢失的问题，所以二分里面的pow要自己写……………….

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a,b,c;
ll qkpow(ll x,int p)
{
	if(p==0) return 1;
	if(p==1) return x; 
	
	ll y=qkpow(x,p>>1);
	
	y=y*y;
	
	if(p&1) 
	y=y*x;
	
	return y;
}
int main()
{
	cin>>a>>b>>c;
	ll l=0,r=(ll)pow((double)c,1.0/a);
	//if(b!=0) r=c/b;
	//r=min(r,(ll)pow(c,1.0/a));
	while(r-l>1)
	{
		ll mid=(r+l)>>1;
		if(qkpow(mid,a)+b*mid<=c)
		{
			l=mid;	
		}
		else
		{
			r=mid;
		}
	}	
	if(qkpow(r,a)+r*b<=c) cout<<r;

… Read the rest

【数学-贪心-末状态已知】问题集合

蓝书 P4 分金币

https://vjudge.net/problem/UVA-11300

关于本题的“想一想为什么”：因为非齐次方程组的系数行列式为0，所以方程的解不唯一，所以最后一个方程没有贡献。

末态相同的题目，可以往方程组方向去想。最后可以往坐标的距离方面去靠。

蓝书 P7 雕塑

本题第一个设想“有一个雕塑不会动”的证明：

设开始每个墓碑相差A，移动后每个墓碑相差M，M可以不相同，因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

[latex][/latex] $A-X_1+X_2=M =X_2=X_1-(A-M)$

$A-X_2+X_3=M =X_3=X_1-2(A-M)$

$\dots$

$A-X_n+X_1=M =X_n=X_1-n(A-M)$

同样可以变成X1到各个数字的距离最小的问题，即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案，因为M仅仅是假设存在一个M使其满足末态，由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解… Read the rest

C#实现俄罗斯方块AI

QQ20170304232315

这个脑洞起源于一道题目。大意是有固定的格子，制作一个AI来让游戏不死。

这题的格子很少，于是可以分类讨论，只要8种情况（好像是？）

先后我去找了一些资料。
发现实现AI的大概思路都是利用启发函数来得到每种状态每个位置的最优解，只考虑当前的一个方块。
对于俄罗斯方块游戏的设计，我用了wiki上面的规定和游戏规则：
1.10个格子宽+22个格子的高，通常情况下21-22个格子被挡住。
2.有 “I”, “O”, “J”, “L”, “S”, “Z”, “T”.七种方块。
3.允许获得下一个方块的形状（因为我设计的AI不许要考虑下一个方块，所以我没有在界面中实现）
4.更多具体参见：http://tetris.wikia.com/wiki/Tetris_Guideline

游戏部分具体的实现不细说，方法很多。
AI部分：
我试过多种启发，后来找到了一种Pierre Dellacherie’s Algorithm，这里我主要说。
这种算法有如下评价
1.Landing Height）：本次下落的方块中点地板的距离
2.Row eliminiated)：本次下落后此方块贡献（参与完整行组成的个数）*完整行的行数
3.Row transitions）：在同一行，方块从无到有或从有到无算一次（边界算有方块）
4.Column transition）：在同一列，方块从无到有或从有到无算一次（边界算有方块）
5.Hole num）：空洞的数量。空洞无论有多大，只算一个。一个图中可能有多个空洞
6.Well sum）：井就是两边都有方块的空列。（空洞也可以是井，一列中可能有多个井）。此值为所有的井以1为公差首项为1的等差数列的总和
例：共三个井，2，3，1 wellsum=（1+2）+（1+2+3）+1；

它们的权值分别为