| by XianKa | No comments

【坑】高数满分—pow的问题

Description

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

Input

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

Output

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

Sample Input

2 3 4

Sample Output

1
这题虽然是一道二分,但由于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
Read More
| by XianKa | No comments

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

  • 蓝书 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)

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

 

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

Read More
| by XianKa | No comments

sort自定义comp不影响速度的写法

inline bool comp(const int &a,const int &b)
{
    return a>b;
}

 … Read the rest

Read More
| by XianKa | No comments

【优先队列-贪心】问题集合

  • 中间商优化

http://codeforces.com/problemset/problem/867/E

一个长度为N的序列,代表每天股票的价格,每天只能执行 买/卖/无动作 三种操作。问如何才能赚得最多。

维护一个优先队列,队首存当前最小的价格,见到比最小的价格高的就先卖掉,并且把低价股票的价格变成当前价格,更低的就进队。如果以后遇到更高的可以和交易过的股票交易,也可以和没交易过的股票交易,它们赚的钱是一样的。。经过xyjj的指点知道了这类题的做法叫中间商优化,先找到更高的卖了提升价格,以后可以继续交易。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector> 
#include<utility>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > b;

ll n,t;
ll ans=0;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		b.push(t);
		if(b.top()<t)
		{
			ans+=t-b.top();
			b.pop();
			b.push(t);
		}
	}
	printf("%lld",ans);
}

 … Read the rest

Read More
| by XianKa | No comments

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;

它们的权值分别为

1
-4.500158825082766
2
3.4181268101392694
3
-3.2178882868487753
4
-9.348695305445199
5
-7.899265427351652
6
-3.3855972247263626

分数为所有评价和权值的乘积的和
经过多次实验发现这个启发非常可靠。在目前的测试看来100W行后还在稳定运行。

 

AItetris源码

参考资料:

http://imake.ninja/el-tetris-an-improvement-on-pierre-dellacheries-algorithm/

Tetris AI – The (Near) Perfect Bot

 

 … Read the rest

Read More
| by XianKa | No comments

2017寒假培训简记

Read the rest Read More
| by XianKa | 2 comments

c#实现马赛克拼图

这个本来是很久以前做出来的东西。前几天有人说用着有问题。就顺便改进了一下。加了多线程。也加了文件过滤。功能还是和一样的。

做着玩儿的玩意儿。

源码点此下载

m

一如既往的textbox+button上下风格…….

相关讨论可去论坛

论坛传送门

Read the rest Read More
| by XianKa | No comments

2017年蒟蒻要奋斗!

2016年过去了

想想其实也没有做什么特别有意义的事情

博客自从建立不怎么更新

竞赛瞎摸几下键盘拿了个二等

真是颓废

 

不过要特别感谢站长NK一年来一直关心我。生日还送我一只蓝牙耳机

img_2673

寒假要修炼一下。感谢一直支持我的爸爸妈妈。

2017要加油了,蒟蒻要奋斗

psb

 … Read the rest

Read More
| by XianKa | No comments

c#实现XM文件播放/转码

这个脑洞也是很久以前就有的了。今天总算把坑填了。

XM文件就是各种注册机啊修改器啊里面的音乐,出奇的魔性啊,dididi~biubiubiu~很好听嘛………

pg

工具可以实现XM到MP3的格式转换,顺便加了播放功能。

基于bassmod的类库实现,这个类库好像很厉害,暴风之类的都使用的这个库。… Read the rest

Read More
| by XianKa | 2 comments

今天搭建了自己的小站

感谢NK站长提供的帮助,今天搭建了自己的小站,开心。

29

以后会在这里面写一些自己觉得有必要记下来的事情,备份自己的小作品,和一些心得经验吧。

晚安!… Read the rest

Read More