A. New Year and Naming
分别取模。
#include <bits/stdc++.h>
using namespace std;
char ss[25][20],tt[25][20];
int main()
{
int n,m,q,k;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%s",ss[i]);
for(int i=0;i<m;i++)
scanf("%s",tt[i]);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d",&k);
printf("%s%s\n",ss[(k-1)%n],tt[(k-1)%m]);
}
}
return 0;
}
B. New Year and Ascent Sequence
对于一些序列，本身就可以满足条件。所有无论把它方在哪都可以满足。因此这些序列的对应的种类可以直接算出。
而对于另一些序列，必须放置某些特定的序列的前面或后面 ，对于这些序列。可以把它的最大和最小值分别放在最大值和最小值数组中，然后遍历最大值数组，在最小值数组中用lower_bound(),即可求出其对应的方案数。
在long long上WA了一发。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
int main()
{
int n,l;
while(scanf("%d",&n)!=EOF)
{
int minn,maxn;
int cnt=0,cot=0;
long long ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&l);
int x,y,f=0;
minn=10000000;
maxn=-1;
scanf("%d",&y);
if(y>maxn)
maxn=y;
if(y<minn)
minn=y;
for(int j=2;j<=l;j++)
{
scanf("%d",&x);
if(x>maxn)
maxn=x;
if(x<minn)
minn=x;
if(x>y)
f=1;
y=x;
}
if(!f)
{
a[++cnt]=minn;
b[cnt]=maxn;
}
else
{
ans+=(2*n-2*cot-1);
cot++;
}
}
//cout<<"ans="<<ans<<endl;
sort(a+1,a+1+cnt);
sort(b+1,b+1+cnt);
for(int i=1;i<=cnt;i++)
{
int t=lower_bound(a+1,a+1+cnt,b[i])-a-1;
ans+=t;//cout<<"t="<<t<<endl;
}
printf("%lld\n",ans);
}
return 0;
}
C. New Year and Permutation
一开始没有想到往排列组合这方面想，一直以为要找规律来推公式。
根据排列组合推导公式为：
对于r-l=i的序列其合理的排列个数为：(n-i) * (i+1) * (n-i)!
预处理一下全排列，然后循环一下即可。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+6e4;
typedef long long ll;
ll a[N];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
ll ans=0;
a[0]=1;
for(int i=1;i<=n;i++)
a[i]=(a[i-1]*(i%m))%m;
for(int i=0;i<n;i++)
ans=(ans+(n-i)*(a[n-i]*a[i+1]%m))%m;
printf("%lld\n",ans%m);
}
return 0;
}
【好题】D. New Year and Conference
题意大概：
对于任意两个事件如果在一个一种情况下是交叉的，那么在另一个情况下必定相交。
如果不符合，输出NO;否则，输出YES。
方法1：
基本思路：
以一个情况下的当前区间交叉情况为基准，同时判断另一个是否相同，一直到全部判断完。
采用stld的multiset维护。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int sa[N],ea[N],sb[N],eb[N];
int n;
struct node
{
int t,s,e,is_in;//t:表示在另一个区间中的开始时间和结束时间，s,e分别表示在当前情况下的开始和结束时间，is_in表示该区间初始一个放进判断范围还是拿出。
};
bool cmp(node x,node y)
{
if(x.t==y.t)
return x.is_in<y.is_in;//
return x.t<y.t;//排序时按，在另一种情况中的开始，结束时间为优先，
}
bool check(int a[],int b[],int c[],int d[])
{
vector<node>lecture;
multiset<int>ss,ee;//
for(int i=1;i<=n;i++)
{//把一个区间在另一个情况下的开始，结束拆开，便于随时维护
lecture.push_back({a[i],c[i],d[i],1});
lecture.push_back({b[i]+1,c[i],d[i],0});//注意+1
}
sort(lecture.begin(),lecture.end(),cmp);
for(int i=0;i<lecture.size();i++)
{//cout<<lecture[i].s<<" "<<lecture[i].e<<endl;
if(lecture[i].is_in)//如果该放入
{
if(!ss.empty())
{
int smax=*ss.rbegin();//最大的开始时间
int emin=*ee.begin();//最小的结束时间
if(lecture[i].s>emin||lecture[i].e<smax)
return false;//没有和所有的区间交叉
}
ss.insert(lecture[i].s);//插入
ee.insert(lecture[i].e);
}
else//该取出
{
ss.erase(ss.find(lecture[i].s));
ee.erase(ee.find(lecture[i].e));
}
}
return true;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&sa[i],&ea[i],&sb[i],&eb[i]);
if(check(sa,ea,sb,eb)&&check(sb,eb,sa,ea))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
方法2：
基本思想和方法1相同，不同的是此处采用线段树维护，关键点在于对时间点进行枚举。
好久没有写线段树的我，写起来还是犯了不少错 >_<。
#include <bits/stdc++.h>
using namespace std;
const int N=4e5+5;//注意数组大小
int tree[N<<2],lazy[N<<2];
int n,len;
struct node
{
int l,r,num;
}a[N],b[N];
vector<int>all,tp1[N],tp2[N];
void build(int l,int r,int rt)
{
if(l==r)
{
tree[rt]=0;
lazy[rt]=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
tree[rt]=0;
lazy[rt]=0;
}
void pushdown(int rt)
{
if(lazy[rt])
{
tree[rt<<1]+=lazy[rt];
tree[rt<<1|1]+=lazy[rt];
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
}
void update(int L,int R,int val,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
tree[rt]+=val;
lazy[rt]+=val;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)
update(L,R,val,l,mid,rt<<1);
if(R>mid)
update(L,R,val,mid+1,r,rt<<1|1);
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
return tree[rt];
int mid=(l+r)>>1;
int ans=0;
pushdown(rt);
if(L<=mid)
ans=max(ans,query(L,R,l,mid,rt<<1));
if(R>mid)
ans=max(ans,query(L,R,mid+1,r,rt<<1|1));
return ans;
}
bool check(node x[],node y[])
{
for(int i=0;i<N;i++)//巧妙之处，两个邻接表的使用
{
tp1[i].clear();
tp2[i].clear();
}
int cnt=0;//存当前判断时，x的交叉的区间个数，与用线段树维护的y的当前交叉的区间个数比较
build(1,len,1);
for(int i=1;i<=n;i++)
{
tp1[x[i].l].push_back(i);//存该时间点对应的时间段的开始时间
tp2[x[i].r].push_back(i);//存该时间点对应的时间段的开始时间
}
for(int i=1;i<=len;i++)//枚举时间点，关键
{
for(int j=0;j<tp1[i].size();j++)//开始时间
{
int id=x[tp1[i][j]].num;//找到此点对应的编号
int ans=query(y[id].l,y[id].r,1,len,1);//查询最大值
if(ans!=cnt)
return false;
update(y[id].l,y[id].r,1,1,len,1);//插入区间
cnt++;
}
for(int j=0;j<tp2[i].size();j++)//结束时间
{
int id=x[tp2[i][j]].num;
update(y[id].l,y[id].r,-1,1,len,1);//删除区间
cnt--;
}
}
return true;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
all.clear();
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].l,&a[i].r,&b[i].l,&b[i].r);
all.push_back(a[i].l);
all.push_back(a[i].r);
all.push_back(b[i].l);
all.push_back(b[i].r);
a[i].num=i;
b[i].num=i;
}//离散化:
sort(all.begin(),all.end());//排序
len=unique(all.begin(),all.end())-all.begin();//去重，len为有效的数据的长度
for(int i=1;i<=n;i++)//二分查找
{
a[i].l=lower_bound(all.begin(),all.begin()+len,a[i].l)-all.begin()+1;//线段树维护区间从1开始
a[i].r=lower_bound(all.begin(),all.begin()+len,a[i].r)-all.begin()+1;
b[i].l=lower_bound(all.begin(),all.begin()+len,b[i].l)-all.begin()+1;
b[i].r=lower_bound(all.begin(),all.begin()+len,b[i].r)-all.begin()+1;
}
if(check(a,b)&&check(b,a))//两次判断
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
持续更新。。。
2020继续加油！
京公网安备 11010502036488号