连号区间数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10,INF=1<<30;
int q[N];
int res;
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++)cin>>q[i];
for(int i=0;i<n;i++){
int maxv=-INF,minv=INF;
for(int j=i;j<n;j++){
maxv=max(maxv,q[j]);
minv=min(minv,q[j]);
if(maxv-minv==j-i)res++;
}
}
cout << res << endl;
return 0;
}
递增三元组
暴力（过了50%）
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
int n;
typedef long long LL;
LL cnt;
int main(){
cin >> n;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++)scanf("%d",&b[i]);
for(int i=0;i<n;i++)scanf("%d",&c[i]);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(a[i]<b[j] && b[j]<c[k])cnt++;
}
}
}
cout << cnt << endl;
return 0;
}
sort+二分
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
int n;
typedef long long LL;
LL cnt;
int bs1(int l,int r,int x){
while(l<r){
int mid = l+r+1>>1;
if(a[mid]<x)l=mid;
else r=mid-1;
}
return a[l]<x?l:-1;
}
int bs2(int l,int r,int x){
while(l<r){
int mid = l+r>>1;
if(c[mid]>x)r=mid;
else l=mid+1;
}
return c[l]>x?l:-1;
}
int main(){
cin >> n;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++)scanf("%d",&b[i]);
for(int i=0;i<n;i++)scanf("%d",&c[i]);
sort(a,a+n),sort(b,b+n),sort(c,c+n);
for(int i=0;i<n;i++){
int l = bs1(0,n-1,b[i]);
int r = bs2(0,n-1,b[i]);
// printf("l:%d r:%d
",l,r);
if(l==-1 || r==-1)continue;
cnt += (LL)(l+1)*(n-r);
}
cout << cnt << endl;
return 0;
}
特别数的和
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e4+10;
int n;
bool check(int x){
while(x){
int t=x%10;
if(t==2 || t==0 || t==1 || t==9)
return true;
x/=10;
}
return false;
}
int main(){
cin >> n;
LL ans=0;
for(int i=1;i<=n;i++)
if(check(i))ans +=i;
cout << ans << endl;
return 0;
}
错误票据
#include<sstream>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int q[N];
int t,n;
int main(){
cin >> t;
getchar();
while(t--){
string s;
getline(cin,s);
stringstream ssin(s);
while(ssin >> q[n])n++;
}
sort(q,q+n);
int a,b;
for(int i=1;i<n;i++){
if(q[i]==q[i-1])b=q[i];
else if(q[i]!=q[i-1]+1)a=q[i]-1;
}
cout << a << " " << b << endl;
}
回文日期
#include<iostream>
using namespace std;
int months[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int res;
bool is_leap(int y){
return y%400==0 || (y%4==0 && y%100!=0);
}
bool check(int date){
int y=date/10000,m=date/100%100,d=date%100;
if(m<1 || m>12)return false;
if(d<1 ||(m!=2 && d>months[m]))return false;
if(m==2){
if(d<1 || d>months[m]+is_leap(y))return false;
}
return true;
}
int main(){
int date1,date2;
cin >> date1 >> date2;
for(int i=1000;i<10000;i++){
int date=i,x=i;
while(x)date = date*10 + x%10,x/=10;
if(date1<= date && date<=date2 && check(date))res++;
}
cout << res << endl;
return 0;
}
归并排序
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q[N],tmp[N];
void merge_sort(int q[],int l,int r){
if(l>=r)return;
int mid = l+r>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r){
if(q[i]<=q[j])tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}
int main(){
cin >> n;
for(int i=0;i<n;i++)
scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",q[i]);
}
return 0;
}
移动距离
#include<iostream>
using namespace std;
int w,m,n;
int main(){
cin >> w >> m >> n;
m--,n--;
int x1=m/w,y1=m%w,x2=n/w,y2=n%w;
if(x1&1)y1=w-y1-1;
if(x2&1)y2=w-y2-1;
int res = abs(x1-x2) + abs(y1-y2);
cout << res << endl;
return 0;
}
日期问题
#include<iostream>
#include<cstring>
using namespace std;
int months[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_leap(int y){
return y%400==0 || (y%4==0 && y%100!=0);
}
bool check(int y,int m,int d){
if(m<1 || m>12)return false;
if(d<1 || (m!=2 && d>months[m]))return false;
if(m==2){
if(d<1 || d>months[m]+is_leap(y))return false;
}
return true;
}
int main(){
int a,b,c;
scanf("%d/%d/%d",&a,&b,&c);
for(int date=19600101;date<=20591231;date++){
int y=date/10000,m=date/100%100,d=date%100;
if(check(y,m,d)){
if((y%100==a && m==b && d==c) ||
(y%100==c && m==a && d==b) ||
(y%100==c && m==b && d==a))
printf("%d-%02d-%02d
",y,m,d);
}
}
return 0;
}
航班时间
#include<iostream>
using namespace std;
int gettime(){
int h1,m1,s1,h2,m2,s2,d=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
return d*24*3600+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);
}
int main(){
int t;
cin >> t;
while(t--){
int t1=gettime(),t2=gettime();
int t=(t1+t2)/2;
printf("%02d:%02d:%02d
",t/3600,t%3600/60,t%3600%60);
}
return 0;
}
外卖店的优先级
暴力（7/10）
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=1e5+10;
int n,m,t;
vector<int> order[N];
int yx[N];
set<int> cache; // 缓存id
bool st[N];
int main(){
cin >> n >> m >> t;
for(int i=0;i<m;i++){
int ts,id;
scanf("%d%d",&ts,&id);
order[ts].push_back(id);
}
for(int i=1;i<=t;i++){ // 枚举时间
memset(st,0,sizeof st);
// 该时刻有订单的店铺+2
for(int k=0;k<order[i].size();k++){
int id = order[i][k];
st[id]=true;
yx[id]+=2;
}
for(int i=1;i<=n;i++)
if(!st[i] && yx[i])yx[i]-=1;
// 遍历店铺,如果优先级>5加入cache,<=3踢出cache
for(int j=1;j<=n;j++){
if(yx[j]>5)cache.insert(j);
if(yx[j]<=3)cache.erase(j);
}
}
cout << cache.size() << endl;
return 0;
}
逆序对的数量
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,q[N],tmp[N];
LL merge_sort(int q[],int l,int r){
LL res=0;
if(l>=r)return 0;
int mid=l+r>>1;
res+=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r){
if(q[i]<=q[j])tmp[k++]=q[i++];
else tmp[k++]=q[j++],res+=mid-i+1;
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
return res;
}
int main(){
cin >> n;
for(int i=0;i<n;i++)
scanf("%d",&q[i]);
LL res = merge_sort(q,0,n-1);
cout << res << endl;
return 0;
}