[CSP-J 2021] 分糖果
题意就不说的
我的做法是二分。
我们要找最大,那么就找n-1
令
如果存在 使得
那么大答案就是
如果不存在这样的,那么只能
洛谷自测100分,时间复杂度
#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
const int MAXR = 1e9+10;
int n,l,r;
signed main(void){
cin >> n >> l >> r;
int ll = 1;
int rr = MAXR;
int temp = n;
while(ll < rr){
int mid = (ll+rr)>>1;
temp = n*mid-1;
if(temp > r){
rr = mid;
}else if(temp >= l && temp <= r){
cout << n-1;
return 0;
}else{
ll = mid+1;
}
}
cout << r%n;
return 0;
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
}
[CSP-J 2021] 插入排序
可过,所以比较简单,注意的是排序的时候不仅要比对元素本身的大小关系,还要比对元素位置大小关系,也就是说,在元素大小相同的情况下,位置靠前的排在前面。
离散化一下记录每个元素的排序后的地点。
由于进行一次 操作,只改变了一个元素的有序性,所以直接向左向右扫一遍看看插在哪儿就完事了。
自测100分
#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
const int MAXN = 1e4;
struct Node{
int v,pos;
bool operator < (const Node & x) const{
return v < x.v;
}
};
vector<Node> a;
vector<Node> b;
int aa[MAXN];
int ls[MAXN];
int ct[MAXN];
int n,q;
bool cmp1(Node x,Node y){
if(x.v == y.v){
return x.pos < y.pos;
}
return x.v < y.v;
}
bool cmp2(Node x,Node y){
return x.pos < y.pos;
}
signed main(void){
// scanf("%lld%lld",&n,&q);
cin >> n >> q;
Node nod;
Node mmin;
mmin.v = -INF;
mmin.pos = 0;
Node mmax;
mmax.v = INF;
mmax.pos = n+1;
a.push_back(mmin);
b.push_back(mmin);
for(int i=1;i<=n;i++){
cin >> nod.v;nod.pos = i;
a.push_back(nod);
b.push_back(nod);
aa[i] = nod.v;
}
a.push_back(mmax);
b.push_back(mmax);
sort(aa+1,aa+1+n);
int cnt = unique(aa+1,aa+1+n) - aa - 1;
for(int i=1;i<=n;i++){
ls[i] = lower_bound(aa+1,aa+1+cnt,b[i].v) - aa;
}
sort(a.begin(),a.end(),cmp1);
for(int i=1;i<=n;i++){
b[i].pos = lower_bound(a.begin(),a.end(),b[i]) - a.begin() + ct[ls[i]];
ct[ls[i]]++;
}
int op,x;
Node v;
while(q--){
scanf("%lld%lld",&op,&x);
if(op==1){
scanf("%lld",&(v.v));
int pps = b[x].pos;
int ppps;
b[x].v = v.v;
a[pps].v = v.v;
for(int i=pps;i<n;i++){
if(a[i].v > a[i+1].v){
b[a[i].pos].pos++;
b[a[i+1].pos].pos--;
Node temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}else if(a[i].v == a[i+1].v){
if(a[i].pos > a[i+1].pos){
b[a[i].pos].pos++;
b[a[i+1].pos].pos--;
Node temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}
}
for(int i=pps;i>=1;i--){
if(a[i].v < a[i-1].v){
b[a[i].pos].pos--;
b[a[i-1].pos].pos++;
Node temp = a[i];
a[i] = a[i-1];
a[i-1] = temp;
}else if(a[i].v == a[i-1].v){
if(a[i].pos < a[i-1].pos){
b[a[i].pos].pos--;
b[a[i-1].pos].pos++;
Node temp = a[i];
a[i] = a[i-1];
a[i-1] = temp;
}
}
}
}else{
printf("%lld\n",b[x].pos);
}
}
return 0;
}
[CSP-J 2021] 小熊的果篮
题意略过
这题用 做,模拟每个块。如果当前块之后的那个块的元素相同,那么合并起来。然后删除后面那个块。如果当前块元素为空,那么直接删除本块。
由于 的合并(
)和删除(
或者
)操作时间复杂度都是
,所以这个算法的整体时间复杂度为
不要用 ,因为
的合并(
)和删除(
)的时间复杂度都是
,用了
后的时间复杂度会退化到
#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <list>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
const int MAXN = 2e5+7;
int n;
struct Node{
int v,pos;
bool operator<(const Node &x) const{
if(v==x.v){
return pos < x.pos;
}
return v < x.v;
}
}a[MAXN];
// vector<vector<Node> > p;
list<list<Node> > ls;
// void ptp(){
// int len = p.size();
// for(int i=0;i<len;i++){
// int len2 = p[i].size();
// for(int j=0;j<len2;j++){
// printf("%lld ",p[i][j].v);
// }
// printf("\n");
// }
// }
void ptls(){
for(auto it = ls.begin();it != ls.end();it++){
for(auto iit = (*it).begin();iit != (*it).end();iit++){
printf("%lld ",iit->v);
}
printf("\n");
}
}
signed main(void){
// freopen("in.in","r",stdin);
// freopen("res.out","w",stdout);
scanf("%lld",&n);
int pre = -1;
int cnt = -1;
int v;
auto it = ls.begin();
for(int i=1;i<=n;i++){
scanf("%lld",&v);
a[i].v = v;
a[i].pos = i;
if(a[i].v != pre){
//不等于前面的,代表要创建一个新的块
cnt++;
vector<Node> temp;
list<Node> tp;
// p.push_back(temp);
ls.push_back(tp);
if(cnt == 0){
it = ls.begin();
}else{
it++;
}
}
// p[cnt].push_back(a[i]);
it->push_back(a[i]);
pre = a[i].v;
}
// ptls();
// while(!p.empty()){
// // cout << "***" << endl;
// // ptp();
// // cout << "***" << endl;
// for(int i=0;i<=cnt;i++){
// if(!p[i].empty()){
// printf("%lld ",p[i][0].pos);
// while(i+1<=cnt){
// if(p[i][0].v == p[i+1][0].v){
// p[i].insert(p[i].end(),p[i+1].begin(),p[i+1].end());
// p.erase(p.begin()+i+1);
// cnt--;
// }else{
// break;
// }
// }
// p[i].erase(p[i].begin());
// if(p[i].empty()){
// p.erase(p.begin()+i);
// i--;
// cnt--;
// continue;
// }
// }else{
// p.erase(p.begin()+i);
// i--;
// cnt--;
// continue;
// }
// }
// printf("\n");
// }
while(!ls.empty()){
// cout << "***" << endl;
// ptls();
// cout << "***" << endl;
for(auto i=ls.begin();i != ls.end();i++){
if(!(i->empty())){
auto itt = i;
auto ttp = i;
printf("%lld ",i->front().pos);
while(++ttp != ls.end()){
if(itt->front().v == ttp->front().v){
itt->splice(itt->end(),*ttp,ttp->begin(),ttp->end());
ls.erase(ttp);
ttp = i;
}else{
break;
}
}
i->pop_front();
if(i->empty()){
i = ls.erase(i);
i--;
continue;
}
}
}
printf("\n");
}
return 0;
}
第三题
题目太长,没做