负载均衡
有 $n$ 台计算机，第 $i$ 台计算机的运算能力为 $v_i$。
有一系列的任务被指派到各个计算机上，第 $i$ 个任务在 $a_i$ 时刻分配，指定计算机编号为 $b_i$，耗时为 $c_i$ 且算力消耗为 $d_i$。
如果此任务成功分配，将立刻开始运行，期间持续占用 $b_i$ 号计算机 $d_i$ 的算力，持续 $c_i$ 秒。
对于每次任务分配，如果计算机剩余的运算能力不足则输出 $−1$，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。
输入格式
输入的第一行包含两个整数 $n, m$，分别表示计算机数目和要分配的任务数。
第二行包含 $n$ 个整数 $v_1, v_2, · · · v_n$，分别表示每个计算机的运算能力。
接下来 $m$ 行每行 $4$ 个整数 $a_i, b_i, c_i, d_i$，意义如上所述。数据保证 $a_i$ 严格递增，即 $a_i < a_{i+1}$。
输出格式
输出 $m$ 行，每行包含一个数，对应每次任务分配的结果。
数据范围
对于 $20%$ 的评测用例，$n, m ≤ 200$。
对于 $40%$ 的评测用例，$n, m ≤ 2000$。
对于所有评测用例，$1 ≤ n, m ≤ 200000，1 ≤ a_i, c_i, d_i, v_i ≤ 10^9，1 ≤ b_i ≤ n$。
输入样例：
2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4输出样例：
2
-1
-1
1
-1
0样例解释
时刻 $1$，第 $1$ 个任务被分配到第 $1$ 台计算机，耗时为 $5$，这个任务时刻 $6$ 会结束，占用计算机 $1$ 的算力 $3$。
时刻 $2$，第 $2$ 个任务需要的算力不足，所以分配失败了。
时刻 $3$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，剩余算力不足 $3$，所以失败。
时刻 $4$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，但剩余算力足够，分配后剩余算力 $1$。
时刻 $5$，第 $1$ 个计算机仍然正在计算第 $1, 4$ 个任务，剩余算力不足 $4$，失败。
时刻 $6$，第 $1$ 个计算机仍然正在计算第 $4$ 个任务，剩余算力足够，且恰好用完。
题解：
有优先队列进行模拟。队列里面是个pair类型，存放着结束时间和需求算力
#include<iostream>
#include<queue>
using namespace std;
const int N = 2000010;
int a[N];
typedef pair<int,int> p;
priority_queue<p,vector<p>> q[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++) cin>>a[i];
while(m--)
{
int x,b,c,d;
cin>>x>>b>>c>>d;
while(q[b].size()&&q[b].top().first<=x)
{
a[b]+=q[b].top().second;
q[b].pop();
}
if(a[b]<d) cout<<"-1"<<endl;
else{
q[b].push(make_pair(x+c,d));//加入任务
a[b] -= d;//更新算力
printf("%d\n",a[b]);//输出算力
}
}
}完全平方数
一个整数 $a$ 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 $b$，使得 $a = b^2$。
给定一个正整数 $n$，请找到最小的正整数 $x$，使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 $n$。
输出格式
输出找到的最小的正整数 $x$。
数据范围
对于 $30%$ 的评测用例，$1 ≤ n ≤ 1000$，答案不超过 $1000$。
对于 $60%$ 的评测用例，$1 ≤ n ≤ 10^8$，答案不超过 $10^8$。
对于所有评测用例，$1 ≤ n ≤ 10^{12}$，答案不超过 $10^{12}$。
输入样例1：
12输出样例1：
3输入样例2：
15输出样例2：
15题解：
数论问题，一个数可以分成多个素数的乘积，那么我们只要让这些素数都是成偶次方呈现就可以了。
对原数进行分解成对个素数，然后答案就是那些不成偶次方素数的乘积。
#include<iostream>
using namespace std;
typedef long long LL;
LL n;
LL res = 1;
int main()
{
cin>>n;
for(LL i = 2;i*i<=n;i++)
{
if(n%i==0)
{
int s = 0;
while(n%i==0)
{
n = n/i;
s++;
}
if(s%2) res*=i;
}
}
if(n>1) res*=n;
cout<<res<<endl;
}平面切分
平面上有 $N$ 条直线，其中第 $i$ 条直线是 $y = A_i · x + B_i$。
请计算这些直线将平面分成了几个部分。
输入格式
第一行包含一个整数 $N$。
以下 $N$ 行，每行包含两个整数 $A_i, B_i$。
输出格式
一个整数代表答案。
数据范围
对于 $50%$ 的评测用例，$1 ≤ N ≤ 4, −10 ≤ A_i, B_i ≤ 10$。
对于所有评测用例，$1 ≤ N ≤ 1000, −100000 ≤ A_i, B_i ≤ 100000$。
输入样例：
3
1 1
2 2
3 3输出样例：
6题解：
#include<bits/stdc++.h>
using namespace std;
long double s[1010][2];//存储直线的A，B
long long ans;
bool st[1010]; //false表示不是重边
pair<long double,long double> p;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>s[i][0]>>s[i][1];
set<pair<long double,long double> > points;
for(int j=0;j<i;j++){
if(st[j])continue;//直线是重边，跳过
if(s[i][0]==s[j][0]){//两条直线斜率相等时，判断是平行还是重合
if(s[i][1]==s[j][1]){
st[i]=true;//待添加直线是重边，退出循环
break;
}else continue;//直线平行，不需要计算交点
}
p.first=(s[j][1]-s[i][1])/(s[i][0]-s[j][0]);//交点的x坐标
p.second=s[i][0]*p.first+s[i][1];//交点的y坐标
points.insert(p);
}
if(!st[i])ans+=points.size()+1;//若当前直线不是重边，更新答案
}
cout<<ans+1;
return 0;
}
回文日期
$2020$ 年春节期间，有一个特殊的日期引起了大家的注意：$2020$ 年 $2$ 月 $2$ 日。
因为如果将这个日期按 “yyyymmdd” 的格式写成一个 $8$ 位数是 20200202，恰好是一个回文数。
我们称这样的日期是回文日期。
有人表示 20200202 是“千年一遇” 的特殊日子。
对此小明很不认同，因为不到 $2$ 年之后就是下一个回文日期：20211202 即 $2021$ 年 $12$ 月 $2$ 日。
也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。
对此小明也不认同，因为大约 $100$ 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 $2121$ 年 $12$ 月 $12$ 日。
算不上“千年一遇”，顶多算“千年两遇”。
给定一个 $8$ 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。
注意
下一个回文日期和下一个 ABABBABA 型的回文日期可能是同一天。
ABABBABA 型的回文日期，需要满足 $A \neq B$。
输入格式
输入包含一个八位整数 $N$，表示日期。
输出格式
输出两行，每行 $1$ 个八位数。
第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。
数据范围
对于所有评测用例，$10000101 ≤ N ≤ 89991231$，保证 $N$ 是一个合法日期的 $8$ 位数表示。
输入样例：
20200202输出样例：
20211202
21211212题解：
#include<iostream>
using namespace std;
int month[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool st1,st2;
int ans1,ans2;
bool checkdata(int a)
{
int y = a/10000;
int m = (a%10000)/100;
int d = a%100;
if(y%4==0&&y%100!=0||y%400==0)
{
month[2] = 29;
}
if(m<0||m>12) return false;
if(d<0||d>month[m]) return false;
return true;
}
int check_ABAB(int n)
{
int a = n / 10000000 , b = n / 1000000 % 10 , c = n /100000 % 10 , d = n / 10000 % 10;
if(a == c && b == d && a != b) return true;
return false;
}
int main()
{
int data;
cin>>data;
int year = data/10000;
while(true)
{
int newdata = year;
int temp = year;
for(int i = 1;i<=4;i++)
{
newdata = newdata*10+ temp%10;
temp/=10;
}
if(newdata==data)
{
year++;
continue;
}
if(checkdata(newdata))
{
if(!st1)
{
st1 = true;
ans1 = newdata;
cout<<ans1<<endl;
}
}
if(checkdata(newdata)&&check_ABAB(newdata))
{
if(!st2)
{
st2 = true;
ans2 = newdata;
cout<<ans2<<endl;
}
}
year++;
if(st1&&st2) break;
}
}括号序列
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。
输入格式
输入一行包含一个字符串 $s$，表示给定的括号序列，序列中只有左括号和右括号。
输出格式
输出一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$ (即 $10^9 + 7$) 的余数。
数据范围
对于 $40%$ 的评测用例，$|s| ≤ 200$。
对于所有评测用例，$1 ≤ |s| ≤ 5000$。
输入样例：
((()输出样例：
5
