|
应该在推n=8,k=7的时候就该想到这一点了啊，而且k<=n-1,看到这个条件了我愣是没往这个地方想：n-1和其他数与就是其他数，就该抽一下自己发困的脑子，，先看一下8进制的真值表会发现0&n-1,2&n-2...i&n-i-1都是为零的，所以我们再看一下k<=n-2的情况，我们可以把k与上n-1，这样就出来k了，然后与k对应的有一个与他相与为零的数b，n-1也对应着一个，而n-1对应的是0，所以我们可以把n-1和b交换一下位置，这样0和b相与还是为0，而n-1就和k相与为k了；再看k==n-1的时候，我们还可以发现从2开始,2&3,3&4...i&(i+1),都是2的倍数，并且是2,4,6,8这样排列的，知道这个规律我们就可以取2，3，n-4,n-3,你会发现这两组与起来的和是n-2,而那个1，我们要借助0,1,n-2,n-1来实现，0&(n-2),1&(n-1)正好和为1，而2，3，n-4,n-3我们只要把3和n-3的位置换一下就能出来n-2了
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
int t,n,k,a[100005];
int main(){
//freopen("in.txt","r",stdin);
cin>>t;
while(t--){
cin>>n>>k;
for(int i=0;i<n;i++) a[i]=i;
if(n==4&&k==3){
cout<<-1<<endl;
continue;
}
if(k==n-1){
swap(a[3],a[n-3]);
swap(a[n-1],a[n-2]);
}
else{
swap(a[n-1],a[n-k-1]);
}
for(int i=0;i<n/2;i++)
cout<<a[i]<<" "<<a[n-i-1]<<endl;
}
return 0;
}
p7076 位运算
自己对位运算太不熟悉了，这道题就是统计出m个条件有那些位是1，然后再看看n个动物的位上是否有m个条件位上的1，有1的该位就变为0就行，最后只要看看条件为上有几个为0，就是2的几次方，最后减个n就可以了，，，，脑子不清晰了，看看博客就明白了
题解 P7076 【动物园（洛谷民间数据）】 - OMG_wc 的博客 - 洛谷博客 (luogu.com.cn)
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
unsigned ll n,m,c,k,p[1000005],q[1000005],a[1000005],bit[66],ori=1ull;
int main(){
//freopen("in.txt","r",stdin);
cin>>n>>m>>c>>k;
for(int i=1;i<=n;i++) cin>>a[i];
unsigned ll ans=1ull;
for(int i=1;i<=m;i++){
cin>>p[i]>>q[i];
bit[p[i]]=1;
}
for(int i=1;i<=n;i++)
for(int j=0;j<k;j++){
if(bit[j]==0) continue;
if((a[i]>>j)&1)
bit[j]=0;
}
for(int i=0;i<k;i++)
if(!bit[i]) ans<<=1;
if(n==0&&k==64){cout<<"18446744073709551616"<<endl;return 0;}
cout<<ans-n<<endl;
return 0;
}
p7095 二分，优先队列
现根据力量进行排序（因为精神是以力量为前提的），二分也可以，直接贪心也可以，都能算出力量的最小值；然后重点是精神，我曾经用二分也求出了精神，但不对，不能根据力量的顺序来求精神，这样是错误的，，但我们可以在不打破力量顺序的情况下建一个以精神为关键字的排序，模拟一遍穿装备的过程，如果不需要增加力量就可穿上，那我们就把他压进队列，若穿不上就从队列里找出一个精神需求最小加成最大的装备来穿，直到满足力量需求，到最后所有装备都从队列过一遍之后，再不断进行取出精神需求最小加成最大的装备直到队空
P7095 [yLOI2020] 不离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
ll t,n,mina=0;
struct game{
ll s,b,c,d;
bool operator<(const game &a)const{
if(b==a.b) return d<a.d;
return b>a.b;
}
/*inline bool operator<(const game &x) const {
return b ^ x.b ? b > x.b : d ^ x.d ? d < x.d : s ^ x.s ? s > x.s : c < x.c;
}*/
}a[1000005];
bool cmp1(game a,game e){
if(a.s==e.s) return a.d>e.d;
return a.s<e.s;
}
/*inline bool cmp1(game x, game y) {
return x.s ^ y.s ? x.s < y.s : x.c ^ y.c ? x.c > y.c : x.b ^ y.b ? x.b < y.b : x.d > y.d;
}*/
bool check1(ll x){
for(int i=1;i<=n;i++){
if(x<a[i].s)return 0;
x+=a[i].c;
}
return 1;
}
int main(){
//freopen("in.txt","r",stdin);
cin>>t;
cin>>n;
ll max1=0,max2=0;
for(int i=1;i<=n;i++) cin>>a[i].s>>a[i].b>>a[i].c>>a[i].d,max1=max(max1,a[i].s),max2=max(max2,a[i].b);
ll l=0,r=max1,mid;
sort(a+1,a+n+1,cmp1);
while(l<=r){
mid=l+r>>1;
if(check1(mid)) r=mid-1;
else l=mid+1;
}
mina=l;
ll minb=0,bb=0;
priority_queue<game> q;
for(int i=1;i<=n;i++){
while(mina<a[i].s){
if(bb<q.top().b) minb+=q.top().b-bb,bb=q.top().b;
bb+=q.top().d;mina+=q.top().c;q.pop();
}
if(mina>=a[i].s) q.push(a[i]);
if(i==n){
while(!q.empty()){
if(bb<q.top().b) minb+=q.top().b-bb,bb=q.top().b;
bb+=q.top().d;q.pop();
}
}
}
cout<<l<<" "<<minb<<endl;
return 0;
}
p7108 逆元，快速幂
没想到我自己竟然推出公式来了，虽然没推出最后求你元的公式。。。这道题难点应该就是逆元别的没了。。。
P7108 【移花接木】题解 - Lillia 的墓碑 - 洛谷博客 (luogu.com.cn)
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll getinv(ll a,ll mod){return qpow(a,mod-2);}
ll t,a,b,h;
int main(){
//freopen("in.txt","r",stdin);
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&a,&b,&h);
if(b==1){printf("%lld\n",((a-1)*h+a)%mod);}
else if(a<=b){printf("%lld\n",qpow(b,h)*a%mod);}
else{printf("%lld\n",((qpow(b,h)-1)*(a-b)%mod*getinv(b-1,mod)%mod+a*qpow(b,h)%mod)%mod);}
}
return 0;
}
p7840
首先，题目要求连 n?1?条边，那么每个点的 di??就至少为1?，每连一条边 di??和会增加2，则总和就为 2n?2?，减去每个点的，剩下的di??就为 n?2?。运用贪心思想每次取出di?+1?影响最小的点，统计答案后把它的 di?+1?再加入队列，执行 n?2?这个过程就行了。
P7840 「C.E.L.U-03」重构 - 随便ad 的博客 - 洛谷博客 (luogu.com.cn)
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
ll read() {
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll getinv(ll a,ll mod){return qpow(a,mod-2);}
ll n;
struct fu{
ll d,v;
bool operator<(const fu &a)const{
return (2*d+1)*v>(2*a.d+1)*a.v;
}
}a[300005];
bool cmp(ll a,ll b){return a>b;}
priority_queue<fu>q;
int main(){
//freopen("in.txt","r",stdin);
n=read();
ll ans=0;
for(int i=1;i<=n;i++) a[i].v=read(),a[i].d=1,q.push(a[i]),ans+=a[i].v;
for(int i=1;i<=n-2;i++){
fu tmp=q.top();q.pop();
ans+=(2*tmp.d+1)*tmp.v;
tmp.d++;
q.push(tmp);
}
cout<<ans<<endl;
return 0;
}
/*10
5 4 3 2 -2 -3 -4 -5
5 4 3 2 -2 -3 -4 -5*/
p1570 二分
这个题的check函数挺不好想的sigma(vi)/sigma(ci)>=x，变形推导出sigma(vi-x*ci)>=0，然后就可以根据这个对数组排序，然后选前m个，判断他们的和是否大于0
题解 P1570 【KC喝咖啡】 - 浅色调 的博客 - 洛谷博客 (luogu.com.cn)
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
ll read() {
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll getinv(ll a,ll mod){return qpow(a,mod-2);}
bool cmp(ll a,ll b){return a>b;}
ll n,m;
struct coffe{
double v,c;double val;
bool operator<(const coffe &a)const{
return val>a.val;
}
}a[210];
bool check(double x){
for(int i=1;i<=n;i++) a[i].val=a[i].v-x*a[i].c;
sort(a+1,a+n+1);
double res=0;
for(int i=1;i<=m;i++) res+=a[i].val;
return res>=0;
}
int main(){
//freopen("in.txt","r",stdin);
n=read();m=read();
double l=0,r=0,mid;
for(int i=1;i<=n;i++) a[i].v=read();
for(int i=1;i<=n;i++) a[i].c=read(),r=max(r,a[i].v*1.0/a[i].c);
while(r-l>1e-6){
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.3f",l);
return 0;
}
/*10
5 4 3 2 -2 -3 -4 -5
5 4 3 2 -2 -3 -4 -5*/
p2759 log函数
求x位数的方法：lg(x)+1，，证明：
由于m为正整数，必然存在正整数n使得10^(n-1)<=m<10^n，则m的位数为n，对此不等式取对数得n-1<=lg(m)<n，故m的位数为[lg(m)]+1。
这题数据量大，所以用二分降低复杂度
题解 P2759 【奇怪的函数】 - - 洛谷博客 (luogu.com.cn)
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
ll read() {
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll getinv(ll a,ll mod){return qpow(a,mod-2);}
bool cmp(ll a,ll b){return a>b;}
ll n,l=0,r=2e9,mid;
int main(){
//freopen("in.txt","r",stdin);
n=read();
while(l<r){
mid=l+r>>1;
ll len=mid*log10(1.0*mid)+1;
if(len<n) l=mid+1;
else r=mid;
//cout<<l<<" "<<r<<endl;
}
cout<<l<<endl;
return 0;
}
/*10
5 4 3 2 -2 -3 -4 -5
5 4 3 2 -2 -3 -4 -5*/
p2804 逆序对
其实这应该叫做求顺序对。。。求有几段区间的平均数大于m，则先每个a[i]都减去m，则问题转化成了求有几段区间的平均数大于0，而求出前缀和，问题就又变为有几个i,j满足s[j]-s[i-1]>0,即s[j]>s[i-1],这就转化为求顺序对了
题解 P2804 【神秘数字】 - yukimura83 的博客 - 洛谷博客 (luogu.com.cn)
#include<bits/stdc++.h>
#define ll long long
typedef __int128 LL;
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=92084931;
ll read() {
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll getinv(ll a,ll mod){return qpow(a,mod-2);}
bool cmp(ll a,ll b){return a>b;}
ll n,m,a[200005],sum[200005],ans=0,b[200005];
void Merge(ll l,ll mid,ll r){
ll i=l,j=mid+1,t=0;
while(i<=mid&&j<=r){
if(sum[i]<sum[j]){
b[t++]=sum[j++];
ans=(ans+mid-i+1)%mod;
}
else b[t++]=sum[i++];
}
while(i<=mid) b[t++]=sum[i++];
while(j<=r) b[t++]=sum[j++];
for(i=0;i<t;i++) sum[l+i]=b[i];
}
void Mersort(ll l,ll r){
if(l<r){
ll mid=l+r>>1;
Mersort(l,mid);
Mersort(mid+1,r);
Merge(l,mid,r);
}
}
int main(){
//freopen("in.txt","r",stdin);
sum[0]=0;
n=read();m=read();
for(int i=1;i<=n;i++){
a[i]=read();
a[i]-=m;
sum[i]=sum[i-1]+a[i];
}
Mersort(0,n);
cout<<ans<<endl;
return 0;
}
|