千题目标CategorySubscribe

描述
给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 A_i，求：
min(1≤j<i) ⁡|A_i-A_j|
以及令上式取到最小值的 j（记为 P_i）。若最小值点不唯一，则选择使 A_j 较小的那个。

输入格式
第一行一个整数n，第二行n个数A_1~A_n。

输出格式
n-1行，每行2个用空格隔开的整数。分别表示当i取2~n时，对应的 min(1≤j<i) ⁡|A_i-A_j| 和 P_i 的值。

样例输入
3
1 5 3
样例输出
4 1
2 1
数据范围与约定
对于30%的数据: n<=100
对于70%的数据: n<=10^4
对于100%的数据: n<=10^5, |A_i|<=10^9

一种做法是用set，因为set是有序集合，直接依次插入，每次找比这个数大的和小的，比较一下做差的绝对值。

• 迭代器的使用：
• set的迭代器只支持++和–两种运算
• it++ 和 ++it 是不一样的，前者先返回自己，再运算，后者是先运算再返回自己。在使用的时候需要注意。
• *号解除引用，*(it++) 和 *(++it)也是不一样的。尽管有括号。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
map<int,int> hm;
set<int> st;
int n;
int k[maxn]={0};
int main()
{
    scanf("%d",&n);
    scanf("%d",&k[1]);
    st.insert(k[1]);
    hm[k[1]]=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&k[i]);
        st.insert(k[i]);
        

一个高中学长问的一道题，挺有意思的。也是简单数论

根据同余的加性，（以下以=代替同余号）

由于a+b=b+c(%k),b=b(%k)

所以可以得到a=c(%k)

同理可以得到a=b=c(%k)

所以目标转化为找同余数。由于任意两个相加需要是K的倍数，所以他们的余数必须都为k/2或者0。

设余数为i，在k是偶数的时候余数可以是k/2和k，在k为奇数的时候i只能是k。

算出每组的个数，再组合数算一下。任意m个里取1个有m种排法，取2个有6*C(m,2)种，取3个有A(3,3)*C(m,3)种。答案就是他们加起来。由于解题的时候在上课，所以我并没有写代码，提问者照着我的思路写了，并且AC了…………

是Java，把int改为long long就AC了… Read the rest

http://lx.lanqiao.cn/problem.page?gpid=T459

问题描述
　　模拟程序型计算器，依次输入指令，可能包含的指令有


　　1. 数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
　　2. 运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余
　　3. 进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36)
　　4. 输出指令：'EQUAL'，以当前进制输出结果
　　5. 重置指令：'CLEAR'，清除当前数字


　　指令按照以下规则给出：
　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
　　进制转换指令可能出现在任何地方


　　运算过程中中间变量均为非负整数，且小于2^63。
　　以大写的'A'~'Z'表示10~35
输入格式
　　第1行：1个n，表示指令数量
　　第2..n+1行：每行给出一条指令。指令序列一定以'CLEAR'作为开始，并且满足指令规则
输出格式
　　依次给出每一次'EQUAL'得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

按题意模拟就可以了。由于是整数，所以把所有进制化为十进制计算，省去了自己写运算的东西。输出的时候转再转换一下就可以了。有个坑点是在ADD等运算之间可能转换进制。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,char> eco;
map<char,ll> deco;
int k=10;
ll ans=0;
char num[99];
void init()
{
	for(ll i=0;i<=9;i++)
	{
		eco[i]=i+'0';
		deco[i+'0']=i;
	}
	for(ll i='A';i<='Z';i++)
	{
		eco[i-'A'+10]=i;
		deco[i]=i-'A'+10;
	}
}
ll getnum()
{
	

Description
jswf夺冠后
cc: tql
gj: tggl
mz：tlrxml
frz: bksjs
wjjj: whnzmqa
......
js: ??? 
js: nmflb

————节选自某次mz语等级测试

mz语等级测试即将到来。然而mz语十分难，用词灵活多变，导致作弊人数众多。而防止考生作弊的一个有效的途径是让考生之间保持一定的距离。

某考场有R（行）*C（列）个座位，坐在(r, c)的考生可能会看到(r,c-1)、(r,c+1)、(r-1,c-1)、(r-1,c+1)（即左、右、左前、右前）4个位置的考生的答案。

为了防止这种情况发生，就要保证一个考生周围的这4个位置中无其他考生。

而由于这个考场年久失修，有一些座位已经损坏，是无法使用的。

现在，fls想知道，在保证无人能看到别人答案的前提下，这个考场最多能安排多少名考生？

Input
多组数据

第一行有一个整数T(T<=30)，代表数据组数。

对每组数据，第一行有两个整数R、C(1 <= R, C <= 50)，表示考场规模。

接下来R行，每行有一个长度为C的字符串，描述考场内每个位置。'.'表示该位置可用，'x'则表示已损坏。

Output
对每组数据，输出该考场内最多能安排的考生数。

Sample Input
1
2 3
...
.x.
Sample Output
4

相隔两列的人是看不见对方的。所以把有冲突的座位连边即为二分图。

任意两个冲突的位置只能有一个地方坐人，即任意点只能有一条边相连。边数就是能坐下的人。转化为了最小边覆盖问题。

答案就是 点数-最大匹配数

注意link vis这些变量名有可能会与STL冲突

#include<vector>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string> 
using namespace std;
int dx[]={-1, 0, 1,-1,0,1};
int dy[]={-1,-1,-1, 1,1,1};
char tsr[55][55];
vector<int> G[3025];
int id[55][55];
int visa[3025]={0};
int linka[3025]={0};
int r,c;
int lig(int 

Description
js在ak了一套cf后，打开了一款新出的射击游戏。

这个射击游戏在一个二维平面进行,js控制的人物处于坐标原点(0,0)。平面上共有n只怪物,每个怪物所在的坐标为(x[i], y[i])。js进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。

而高贵的js是这个游戏的VIP玩家,他拥有两项特权操作:
1、让平面内的所有怪物向任意一个相同的方向移动相同的距离d。
2、让平面内的所有怪物以js为中心旋转相同的角度θ。

js在进行射击前,可以无限次的使用这两项特权操作。js想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮伟大的js吧。

Input
输入包括三行。

第一行中有一个正整数n(1 <= n <= 100),表示平面内的怪物数量。

第二行包括n个由空格分隔的整数x[i](-1,000,000 <= x[i] <= 1,000,000),表示每只怪物的横坐标。

第二行包括n个由空格分隔的整数y[i](-1,000,000 <= y[i] <= 1,000,000),表示每只怪物的纵坐标。

Output
输出js一次性最多能消灭的怪物数。

Sample Input
5
0 -1 1 1 -1
0 -1 -1 1 1
Sample Output
5

枚举两个点，连成一条线。每次检查在线上有多少点，不在线上的点往线上作投影，当线上的点+某个投影的坐标的所有点>答案的时候，更新答案。

是否三点一线用向量是否平行，投影也用向量坐标运算。

技巧：投影用map来存储，遍历的时候用map的迭代器进行遍历。重载运算符实现坐标相减得到向量的功能。

答案初始化为1；因为如果没有能构成线点，那么将不运算

#include<bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
struct point{
	ll x, y;
	point(){}
	point(ll x,ll y):x(x),y(y){}
	point operator -(point tp)
	{
		return point(x-tp.x,y-tp.y);
	}
}p[110];
ll dot(point a,point b)
{
	

Description
果苣是一类高贵的水果的统称。

而果苣拼盘则是使用这些高贵的水果制成的拼盘。制作一份果苣拼盘，需要满足如下限制：
     1. 必须使用特定的n种果苣。
     2. 第i种果苣的数量不能少于li 份，也不能多于ri 份
     3. 果苣的总份数要恰好为m份

果苣想知道，一共有多少种不同的果苣拼盘的制作方案？

Input
多组数据

第一行有一个整数T(T<=20)，代表数据组数。

对每组数据，第一行有两个由空格分隔的整数n和m(1<=n<=20, 1<=m<=100)，表示果苣的种类和拼盘需要的果苣总份数。

接下来n行，每行有两个由空格分隔的整数li 和ri (0<= li <= ri <= 10)，描述第i种果苣数量的限制。

Output
对每组数据，输出满足限制条件的方案数。

Sample Input
2
2 3
1 2
1 2
3 5
0 3
0 3
0 3
Sample Output
2
12
HINT
对于两种方案，当有任意一种水果的份数不同时，则两种方案不同。

每种水果无论取几个都只有一种取法。生成函数，最后[latex]x^n[/latex]的系数就是答案，即多项式的乘法。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll a[220][1100]={0};
ll t,n,m,l[220],r[220];
ll ans[1100],tmp[1100];
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		memset(ans,0,sizeof(ans));
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld%lld",&l[i],&r[i]);
			m-=l[i];
			

Description
令F(i)表示斐波那契数列的第i项。
S1(i)表示F数列的前i项和。
S2(i)表示S1数列的前i项和。
S3(i)表示S2数列的前i项和。
S4(i)表示S3数列的前i项和。
S5(i)表示S4数列的前i项和。
S6(i)表示S5数列的前i项和。
S7(i)表示S6数列的前i项和。
S8(i)表示S7数列的前i项和。
求S8(N)。答案可能很大，请对1000000007取模。
斐波那契数列的定义可以查看https://baike.baidu.com/item/斐波那契数列

Input
多组数据。
输入的第一行包括一个整数表示数据组数T(1< =T<=1000)。
每组数据的第一行包括一个整数表示题目所说的N(1<=N<=1000000000000000000)。

Output
每组数据在单独的一行中输出S8(N)。


Sample Input
4
1
2
3
4
Sample Output
1
9
46
175
HINT
F数列前四项：1 1 2 3

S1数列前四项：1 2 4 7

S2数列前四项：1 3 7 14

S3数列前四项：1 4 11 25

S4数列前四项：1 5 16 41

S5数列前四项：1 6 22 63

S6数列前四项：1 7 29 92

S7数列前四项：1 8 37 129

S8数列前四项：1 9 46 175 

由题目给的hint其实已经看出来了[latex]S_n^8=S_{n-1}^{87654321}+F_n[/latex]

其他项也是如此

#include
using namespace std;
typedef long long ll;
ll p=1000000007;
struct Mat{
    ll a[10][10];
    Mat(){
        memset(a,0,sizeof(a));
    }
};
Mat mul(Mat a,Mat b)
{
    Mat res=Mat();
    for(ll i=0;i<10;i++)
    {
        for(ll j=0;j<10;j++)
        {
            for(ll k=0;k<10;k++)
            {
                if(a.a[i][k]&&b.a[k][j])
                res.a[i][j]+=(a.a[i][k]%p)*(b.a[k][j]%p)%p; 
            }   
        }   
    }   
    return res;
} 
Mat ksm(Mat n,ll k)
{
    Mat ans=Mat();
    for(ll i=0;i<10;i++)
    ans.a[i][i]=1;
    while(k)
    {
        if(k&1) ans=mul(n,ans);
        n=mul(n,n);
        k>=1;
    }
    return ans;
}
int main()
{
    ll t;
    ll temp1[10][10]={
        {1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,0},
        {0,0,1,1,1,1,1,1,1,0},
        {0,0,0,1,1,1,1,1,1,0},
        {0,0,0,0,1,1,1,1,1,0},
        {0,0,0,0,0,1,1,1,1,0},
        {0,0,0,0,0,0,1,1,1,0},
        {0,0,0,0,0,0,0,1,1,0},
        {0,0,0,0,0,0,0,0,1,1},
        {0,0,0,0,0,0,0,0,1,0}
        };
    ll temp2[10][10]={
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0}
        };