幸运串

题意:长度为n,字符集大小为m的字符串中有多少不同的不含回文的串

n,m<10^9


我靠这不就是萌数的DP部分吗

有规律

f[2][j][k]=1

f[i][j][k]=sigma{f[i-1][k][z]|z!=j&&z!=k}

答案就是m*(m-1)*(m-2)^(n-2)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MOD=1e9+;
ll n,m;
inline ll powMod(ll a,ll b){
ll ans=;
for(;b;b>>=,a=(a*a)%MOD)
if(b&) ans=(ans*a)%MOD;
return ans;
}
int main(){
freopen("lucky.in","r",stdin);
freopen("lucky.out","w",stdout);
scanf("%lld%lld",&n,&m);
if(m==) printf("%d",n==?:);
else if(n==) printf("%d\n",m);
else printf("%lld",m*(m-)%MOD*powMod(m-,n-)%MOD);
}


最优排名

很明显贪心

先v大到小排序

找之前w-v最小的,送她气球,删掉它;送气球之后加入后面又超过自己的

用set超时了,直接用堆就好,只需要删除最大元素

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
const int N=3e5+;
typedef long long ll;
inline ll read(){
char c=getchar();ll x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n;
struct team{
int id;
ll w,v;
bool operator <(const team &r)const{return v>r.v;}
}a[N]; multiset<ll> s;
int main(){
freopen("rank11.in","r",stdin);
freopen("rank11.out","w",stdout); n=read();
for(int i=;i<=n;i++) a[i].id=i,a[i].v=read(),a[i].w=read();
sort(a+,a++n);
ll p=,rank;
for(int i=;i<=n;i++){
if(a[i].id==) break;
p++;
s.insert(a[i].w-a[i].v+);
}
rank=p+;//printf("rank %d\n",rank);
ll v=a[rank].v,ans=rank,tail=rank+;
while(v&&!s.empty()){
ll now=*s.begin(); //printf("now %d\n",now);
s.erase(s.begin());
if(v-now>=) v-=now,rank--;
while(v<a[tail].v) {s.insert(a[tail].w-a[tail].v+);tail++;rank++;}
ans=min(ans,rank);
}
printf("%d",ans);
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N=3e5+;
typedef long long ll;
inline ll read(){
char c=getchar();ll x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n;
struct team{
int id;
ll w,v;
bool operator <(const team &r)const{return v>r.v;}
}a[N]; priority_queue<ll,vector<ll>,greater<ll> > q;
int main(){
freopen("rank.in","r",stdin);
freopen("rank.out","w",stdout); n=read();
for(int i=;i<=n;i++) a[i].id=i,a[i].v=read(),a[i].w=read();
sort(a+,a++n);
ll p=,rank;
for(int i=;i<=n;i++){
if(a[i].id==) break;
p++;
q.push(a[i].w-a[i].v+);
}
rank=p+;//printf("rank %d\n",rank);
ll v=a[rank].v,ans=rank,tail=rank+;
while(v&&!q.empty()){
ll now=q.top();q.pop();
if(v-now>=) v-=now,rank--;
while(v<a[tail].v) {q.push(a[tail].w-a[tail].v+);tail++;rank++;}
ans=min(ans,rank);
}
printf("%d",ans);
}


运输任务

貌似是树链剖分,不会

能骗20到50分吧

最新文章

  1. GridView嵌套在ScrollView里只有一行的问题
  2. [转载]AxureRP学习成长之路
  3. 嵌套div中margin-top转移问题的解决办法
  4. 李洪强iOS面试题之-iOS选择题
  5. TCP状态转移图学习总结
  6. LeetCode9 Palindrome Number
  7. 29 个 PHP 的 Excel 处理类
  8. 使用Java原生代理实现数据注入
  9. Web API路由与动作(三)
  10. 【转】sqlmap用户手册
  11. 前端-mate讲解
  12. 关于Smartforms换页的
  13. 如何学习ACM
  14. spark的sparkUI如何解读?
  15. Hibernate(十一):映射继承关系的三种方案
  16. Android APP应用启动页白屏(StartingWindow)优化
  17. Python学习:类和实例
  18. C#VS2017添加ReportViewer控件
  19. 三,用户交互方式与python基本数据类型
  20. 并发编程之synchronized关键字

热门文章

  1. 尝试加载 Oracle 客户端库时引发 BadImageFormatException
  2. 浅谈SQL Server中的三种物理连接操作
  3. 如何实现在PHP中调用JAVA
  4. spi 10方式编写
  5. 常用C#关键字详解教程
  6. Disruptor-net 3.3.0
  7. iOS Block界面反向传值
  8. iOS简单实现毛玻璃效果
  9. iOS中的交换空间(swap space)
  10. 基于Server-Sent Event的简单在线聊天室