口罩加工
COVID-19让人沮丧,但是那些勇敢的人还奋战在一线,此刻我也在祈愿.
为了保障物资的生产,许多企业纷纷跨行业生产口罩,假如有n个需要生产口罩的流水线任务,每个任务的执行时间开始为li直到ri结束,每台机器同一时间只能执行一个任务.
请问最少需要多少台机子确保所有生产任务顺利执行.
输入
第一行有一个数代表n个任务
接下来n行每行两个数代表每个任务执行的开始时间li和结束时间ri
输出
一个数字代表最少需要多少台机子
贪心+优先队列
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstdio>
typedef long long ll;
using namespace std;
typedef pair<ll,ll>pii;
const int N=1e6+5;
int n;
pair<ll,ll>a[N];
int main(){
cin>>n;
for(int i=0;i<n;i++)scanf("%lld%lld",&a[i].first,&a[i].second);
sort(a,a+n);
priority_queue<pii,vector<pii>,greater<pii>> heap;
for(int i=0;i<n;i++){
if(heap.empty()||heap.top().first>=a[i].first){
pii s={a[i].second,heap.size()};
heap.push(s);
}
else {
auto s=heap.top();
heap.pop();
s.first=a[i].second;
heap.push(s);
}
}
cout<<heap.size()<<endl;
return 0;
}
.
.
.
传递石头
有n个小朋友站成一排玩游戏，他们每个人手中分别有a1,a2,a3…an 块石头，他们需要通过传递石头来调整手中的石头数目。每个人每次只能给相邻的人传递一块石头。他们不希望一个人拿着多个石头，但又想要让石头分布均匀，所以他们想要通过传递石头，使得每个人最多只拿11块石头，并且每个拿石头的人旁边的人都不拿石头，每个不拿石头的人旁边的人都拿石头。
你能告诉他们想要最少的传递次数吗？如果无法完成任务则输出-1
输入
第一行包含一个整数 T 表示 T 组测试数据，对于每组测试数据：
第一行一个整数 n 表示有 n 个小朋友
第二行 n 个数a1,a2,a3…an ,表示开始时每个小朋友手中的石头数.
1≤T≤10
1≤n≤2x105
0≤ai≤109
输出
对于每组测试样例输出一个数表示最小传递次数或-1
石头最后序列一定为01序列,首先判断石头之和是否满足和小朋友的关系,过多或过少都不行.
两种情况:石头在奇数位置,石头在偶数位置.
以奇数为例,扫描每个位置,奇数位置把该位置的石头数量更新为1,多余往右传,缺少从右边拿,偶数位置把这个石头变为0.
需要把这两种情况都扫描一遍,判断最少移动次数.
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int t,n;
const int N=1e5+5;
int a[2*N];
int main(){
cin>>t;
while(t--){
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum>(n+1)/2||sum<n/2){
cout<<-1<<endl;
continue;
}
ll q=0,ans1=0,x=1;//q为需要的石头,ans为移动次数,x为该位置需要的石头数
for(int i=1;i<=n;i++){
q+=x-a[i];
ans1+=abs(q);
x=1-x;
}
if(q!=0)ans1=0x3f3f3f3f;
ll ans2=0;
q=0,x=0;
for(int i=1;i<=n;i++){
q+=x-a[i];
ans2+=abs(q);
x=1-x;
}
if(q!=0)ans2=0x3f3f3f3f;
cout<<min(ans1,ans2)<<endl;
}
return 0;
}
.
.
.
奇怪的馅饼
有一个坐标系，BaoBao 的家在(n,m) 点,BaoBao 现在在(0,0) 点，坐标系上有 k个奇怪的馅饼，坐标分别为(x1,y1)、(x2,y2)…(xk,yk).这 kk 个馅饼的坐标满足∀i∈{2,3,4,…,k} 都有xi-1≤xi并且yi-1≤yi,BaoBao 想要在回家的过程中将这 k 个馅饼全部拿到，同时还要保证走的步数最少，BaoBao 想要问聪明的你，他一共有几种走法?
答案对100003取模.
输入
第一行一个整数 T 表示有 T 组测试数据。对于每组测试数据:：
第一行包含三个整数 n、m、k
接下来 k 行每行两个整数 (x,y) 表示每个馅饼的坐标
1≤T≤10
0≤n,m≤1018
0≤k≤105
0≤x≤n
0≤y≤m
输出
对于每组测试数据输出一个整数,表示方案数
卢卡斯+快速幂求逆元
**乍一看可能是dfs,但是仔细观察馅饼坐标可以发现,下一个馅饼一定在上一个的右下,所以每两个坐标之间构成n×m的矩阵,相当于询问多个n×m的矩阵从左上角走到右下角有多少种情况(高中排列组合问题) **
存下每个点的坐标,由于数据范围1018暴大,所以用卢卡斯定理处理,再用快速幂求逆元优化一下求的过程(直接抄y总卢卡斯板子无限超时)
血的教训:乘法时随时取模…
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod=100003;
typedef long long ll;
ll t,n,m,k;
const int N=1e5+10;
pair<ll,ll>a[N];
ll fact[N],infact[N];
ll qmi(ll a,ll k,int p){
ll res=1;
while(k){
if(k&1)res=(ll)res*a%p;
a=(ll)a*a%p;
k>>=1;
}
return res;
}
ll c(ll a,ll b,int p){
if(a<b)return 0;
return (ll)fact[a]*infact[b]%p*infact[a-b]%p;
}
ll lucas(ll a,ll b,int p){
if(a<p&&b<p)return c(a,b,p);
return (ll)c(a%p,b%p,p)*lucas(a/p,b/p,p)%mod;
}
int main(){
fact[0]=infact[0]=1;
for(int i=1;i<N;i++){
fact[i]=(ll)fact[i-1]*i%mod;
infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;
}
cin>>t;
while(t--){
memset(a,0,sizeof a);
cin>>n>>m>>k;
a[0].first=0;
a[0].second=0;
a[k+1].first=n;
a[k+1].second=m;
for(int i=1;i<=k;i++){
scanf("%lld%lld",&a[i].first,&a[i].second);
}
ll ans=1;
for(int i=0;i<=k;i++){
ll x=(a[i+1].first+a[i+1].second-a[i].first-a[i].second);
ll y=min(a[i+1].first-a[i].first,a[i+1].second-a[i].second);
ans=ans*lucas(x,y,mod)%mod;
}
cout<<ans<<endl;
}
return 0;
}
.
.
.
函数
BaoBao 打 CF 的时候看到了一个函数，f：f(x, y) = (x | y) - y其中 ∣ 表示按位或。BaoBao 想要进一步研究一下这个函数的性质，于是就有了下面的问题。
BaoBao 有一个长度为 n 的数组 a1、a2、a3…an，他想要找到一个整数 x 使得 f(a1,x)、f(a2,x)、f(a3,x)…f(an,x) 的值都为 0 。但是显然有很多个 x 符合要求，因此BaoBao 想要你帮他找到一个最小的满足要求的 x 。
输入
第一行一个整数 T 表示有 T 组测试数据。对于每组测试数据：
第一行一个整数 n 表示数组长度为 n。
第二行 n 个数，分别为 a1、a2、a3…an
1≤T≤10
1≤n≤2×105
0≤ai≤260
输出
输出一个整数表示答案
有一说一,我对涉及到位运算的题是极为头疼的…当时学的时候就没搞明白,做题时瞎搞加上大佬的指点a掉
附上学长正规做法(感谢学长)
所以将所有的输入或一下即可
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int main(){
int t,n;
cin>>t;
while(t--){
cin>>n;
ll ans=0,x;
for(int i=1;i<=n;i++){
scanf("%lld",&x);
ans=ans|x;
}
cout<<ans<<endl;
}
return 0;
}
.
.
.
.
对于dl来说,这些都是些水题,对于我这个菜鸡来说,是真正第一次用基础算法能写出题来,所以还是感触颇多(有错误还请指教)