| by XianKa | No comments

### 【矩阵快速幂】nth Term LightOJ – 1096

You have to find the nth term of the following function:

f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2)

= 0, if(n ≤ 2)

Input
Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output
For each case, print the case number and f(n) modulo 10007.

Sample Input

| by XianKa | No comments

### 【离线并查集】问题集合

• 有 N 个数，初始均为 0。有 Q 个操作，第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问，所有操作结束后，每个数的值

#include<iostream>
#include<stdio.h>
using namespace std;
int f={0};
int qm={0};
int a={0};
int n=0,q=0;
int ff(int x)
{
if(f[x]==x) return x;
else return f[x]=ff(f[x]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n+2;i++) f[i]=i;
for(int i=q;i>0;i--)
{
scanf("%d%d%d",&qm[i],&qm[i],&qm[i]);
}
for(int i=1;i<=q;i++)
{
int l=qm[i],r=qm[i],v=qm[i];
while(l<=r)
{
l=ff(l);
if(l<=r)
{
a[l]=v;
f[l]=l+1;
l+=1;
}
else
{
break;
}
}
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
} 
| by XianKa | No comments

## Sample Input

2 3 4

## Sample Output

1


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;

| by XianKa | No comments

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

• 蓝书 P4 分金币

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

• 蓝书 P7 雕塑

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)

| by XianKa | No comments

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

inline bool comp(const int &a,const int &b)
{
return a>b;
}
| by XianKa | No comments

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

• 中间商优化

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

#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);
}
| by XianKa | No comments

### C#实现俄罗斯方块AI 1.10个格子宽+22个格子的高，通常情况下21-22个格子被挡住。
2.有 “I”, “O”, “J”, “L”, “S”, “Z”, “T”.七种方块。
3.允许获得下一个方块的形状（因为我设计的AI不许要考虑下一个方块，所以我没有在界面中实现）
4.更多具体参见：http://tetris.wikia.com/wiki/Tetris_Guideline

AI部分：

1.Landing Height）：本次下落的方块中点地板的距离
2.Row eliminiated)：本次下落后此方块贡献（参与完整行组成的个数）*完整行的行数
3.Row transitions）：在同一行，方块 从无到有 或 从有到无 算一次（边界算有方块）
4.Column transition）：在同一列，方块 从无到有 或 从有到无 算一次（边界算有方块）
5.Hole num）：空洞的数量。空洞无论有多大，只算一个。一个图中可能有多个空洞
6.Well sum）：井就是两边都有方块的空列。（空洞也可以是井，一列中可能有多个井）。此值为所有的井以1为公差首项为1的等差数列的总和

 1 -4.50016 2 3.41813 3 -3.21789 4 -9.3487 5 -7.89927 6 -3.3856

AItetris源码

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

Tetris AI – The (Near) Perfect Bot

| by XianKa | No comments

### 2017寒假培训简记

| by XianKa | 2 comments

## 源码点此下载 ## 论坛传送门

| by XianKa | No comments

### 2017年蒟蒻要奋斗！

2016年过去了 2017要加油了，蒟蒻要奋斗 