H Hard Calculation
签到题
J Parallel Sort
分析：很好想到找环 对于每个环 最多两次操作即可还原
构造每个环的方案 ：每次将环脱去一对即可
开始我构造的按照顺序脱去一对 但是只过了70个点 正解为首尾依次脱环
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
struct huan
{
vector<int> sig;//环中数据的位置
int type;//环的型号，一元环为0，2元为1，更多为2
};
int maxtip = 0;//最大环型号
huan allh[100005];//环组
int aback = 0;//环组尾标
int orig[100005];//原始数据
int seat[100005];//i在原始数据中的位置
bool used[100005];//开环时被使用标记
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> orig[i];
seat[orig[i]] = i;
}
//打出所有环
for (int i = 1; i <= n; i++)
{
if (used[i] == 1)
continue;//已经入环的去掉
int t = aback;
aback++;//栈顶移动
allh[t].sig.push_back(i);//环的开头
used[i] = 1;
int j = orig[i];
while (1)
{
if (j != i)//不是环尾
{
allh[t].sig.push_back(j);
used[j] = 1;
j = orig[j];
}
else//是环尾
{
used[j] = 1;
break;//不进入，直接跳出
}
}
//给出类型
int size = allh[t].sig.size();
if (size == 1)
allh[t].type = 0;
else if(size == 2)
allh[t].type = 1;
else
allh[t].type = 2;
maxtip = max(maxtip, allh[t].type);
}
//输出结果
cout << maxtip << endl;
for (int i = maxtip; i > 0; i--)//每一行
{
vector<int> y;//装输出数据的数组
for (int j = 0; j < aback; j++)//遍历每个环
{
if (allh[j].type >= i)//只有等级足够的环才来
{
int right = allh[j].sig.size() - 1;
int left = i == 2 || allh[j].type == 1 ? 0 : 1;
while (left < right)
{
y.push_back(allh[j].sig[left]);
y.push_back(allh[j].sig[right]);
left++;
right--;
}
}
}
cout << y.size() / 2;
for (int k = 0; k < y.size(); k++)
{
cout << " " << y[k];
}
cout << endl;
}
}
L Simone and graph coloring
分析：考虑如果完全降序 整个图即为一个完全图 这样每个点的颜色都需要不同
所以想到对于每个下降子序列的长度就是所需颜色的数量 最长就是答案
至于方案数在求最长下降子序列的过程中跟新
需要用到二分dp来求解
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int T,n,a[N],b[N],ls[N];
int get(int l,int r,int x){
while(l<r){
int mid=(l+r)>>1;
if(ls[mid]>x) l=mid+1;
else r=mid;
}
return l;
}
void solve(){
int tot=0; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(tot==0||a[i]<ls[tot]) ls[b[i]=++tot]=a[i];
else{
int tmp = get(1,tot,a[i]);
b[i] = tmp;
ls[tmp] = a[i];
}
}
cout<<tot<<"\n";
for(int i=1;i<=n;i++) cout<<b[i]<<" \n"[i==n];
}
int main(){
cin>>T;
while(T--) solve();
}
M Stone Games
题意：求静态区间数的选取集合不能构造出的和的最小值，在线
分析：
如果没有1，则凑不出来的最小数为1
否则设有x个1
显然，一定可以凑出[1,x]
注意到如果剩余大于1的数中最小数为k，若k<=x+1
则可以凑出[1,x+k]
推知若当前可以凑出[1,x]，剩余数中所有小于等于x+1的数，均可累加到连续上限中
即凑出[1,x+Σsi(si<=x+1)]
若找不到新增的数，则答案为x+1。
主席树维护区间小于等于某个数的和，可以不初始化直接边插入边建树
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e6+10,inf = 1e9;
int n,m,idx,root[N];
struct Node{
int l,r;
int sum;
}tr[N*50];
int insert(int p,int l,int r,int x){
int q=++idx;
tr[q]=tr[p];
if(l==r){
tr[q].sum+=x;
return q;
}
int mid=l+r>>1;
if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);
else tr[q].r=insert(tr[p].r,mid+1,r,x);
tr[q].sum=tr[tr[q].l].sum+tr[tr[q].r].sum;
return q;
}
int query(int q,int p,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr) return tr[q].sum-tr[p].sum;
if(l>qr||r<ql) return 0;
int mid=l+r>>1;
return query(tr[q].l,tr[p].l,l,mid,ql,qr)+query(tr[q].r,tr[p].r,mid+1,r,ql,qr);
}
signed main(){
cin>>n>>m;
for(int i=1,t;i<=n;i++){
cin>>t;
root[i]=insert(root[i-1],0,inf,t);
}
int res=0;
while(m--){
int l,r;
cin>>l>>r;
l=(res+l)%n+1,r=(res+r)%n+1;
if(l>r) swap(l,r);
int x=query(root[r],root[l-1],0,inf,1,1);
int last=x;
while(1){
int sum=query(root[r],root[l-1],0,inf,1,min(inf,x+1))-last;
if(!sum) break;
x+=sum,last=x;
}
res=x+1;
cout<<res<<endl;
}
return 0;
}
J Mr. Main and Windmills
分析：就是暴力就好 计算几何不在我的范围类
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
LL x1,y1,x2,y2;
LL n,m;
struct node
{
LL x;
LL y;
}N[1001];
vector<double> V[1001];
int main()
{
cin>>n>>m;
cin>>x1>>y1>>x2>>y2;
for(int a=1;a<=n;a++) cin>>N[a].x>>N[a].y;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
{
LL x3=N[i].x,y3=N[i].y,x4=N[j].x,y4=N[j].y;
double t1=(double)(x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
if(t1>0&&t1<1) V[i].push_back(t1);
}
for(int a=1;a<=n;a++) sort(V[a].begin(),V[a].end());
while(m--)
{
int h,k;
cin>>h>>k;
if(k<=V[h].size()) printf("%.6f %.6f\n",x1+V[h][k-1]*(x2-x1),y1+V[h][k-1]*(y2-y1));
else cout<<-1<<"\n";
}
}