好久没写博客了，写篇博客放松一下。
外网OJ：http://csustacm.com:4803/
1题我就不写了这题写了也没啥意义。
2.黄金矿工
Description
游戏中有n个宝石，每个宝石有一个价值vi，每次挖出这个宝石需要时间ti。因为有些宝石被另外一个宝石挡住了（两个宝石在同一直线上），一个宝石最多挡住一个宝石，一个宝石最多被一个宝石挡住。要先捡起挡路的宝石，才能捡起该宝石。每个宝石的挡路宝石为fi，如果没有挡路宝石fi = 0，即它自己(题目保证没有环，且不存在)。
游戏的时间限制是t秒，在t秒内你获得最大价值和是多少？
Input
第一行一个整数T，表示接下来有T组数据。（T <= 50）
每组数据格式如下：
第一行两个整数n（1<=n<=200），t（1<=t<=100,000,000）
接下来n行，每行三个整数vi（1<=vi<=50），ti（1<=ti<=1000,000），（0<=fi<=n）
Output
输出获得的最大价值和
Sample Input 1
1
5 10
2 1 0
5 3 1
3 2 0
1 4 3
4 6 4 Sample Output 1
11 题意：挖宝石，挖某个宝石前可能有一个宝石，一个宝石也只能阻难一个宝石，挖某个宝石要消耗时间ti获得价值vi，问T=t秒最多可以挖宝石的最大价值。
题解：看了下数据范围，肯定是以价值DP，求价值的最小时间，如果时间小于所给定的时间就可以挖到相应价值。
首先处理下，每个宝石前后最多只有一个，肯定是一条链，把每条链处理一下（假如一条链是1->2->3,那么这条链上就有3个节点分别保存2个值，挖到1，(v1,t1）挖到2，（v1+v2,t1+t2）挖到3,(v1+v2+v3,t1+t2+t3))。最多只有200条链，所以不用担心超时。
每条链保存 两个值，价值和所需要的时间。然后在DP就行了。因为每条链上只能选一个值所以DP肯定要开二维。
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#define debug(x) cout<<"["<<x<<"]"<<endl;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const int maxn=1e3+7;
const int inf=0x3f3f3f3f;
int n, m, tot;
int son[maxn];
int in[maxn], v[maxn], t[maxn], vis[maxn];
vector<P> ar[maxn];
int dp[205][10005];
void dfs(int u,int val,int tim) { //用DFS，一条链
vis[u] = 1;
ar[tot].push_back(make_pair(val+v[u],tim+t[u]));
if(son[u] == 0)return;
dfs(son[u],val+v[u],tim+t[u]);
}
int main() {
int tim;
scanf("%d", &tim);
while(tim--) {
scanf("%d%d", &n, &m);
int sum = 0;
for(int i = 0; i <= n; ++i) {
son[i]=vis[i]=0;
ar[i].clear();
}
for(int i = 1, u; i <= n; ++i) {
scanf("%d%d%d", &v[i], &t[i], &u);
sum += v[i];
//if(u == 0)continue;
son[u] = i;
}
tot = 0;
for(int i = 1; i <= n; ++i) {
if(vis[i] == 0) {//如果这个节点没有父亲，就说明这有一条链。
dfs(i, 0, 0);
tot++;
}
}
memset(dp, 0x3f, sizeof(dp));
for(int i = 0; i < tot; ++i) { 。
ar[i].push_back(make_pair(0, 0));//每个链肯定可以一个都不挖，所以0 ，0要加进去。
sort(ar[i].begin(),ar[i].end());
}
int sz = ar[0].size();
for(int i = 0; i < sz; ++i) {//dp初始化
dp[0][ar[0][i].fi] = ar[0][i].se;
}
for(int i = 1; i < tot; ++i) {
sz = ar[i].size();
for(int j = 0; j < sz; ++j) {
for(int k = sum; k >= ar[i][j].fi; --k) {
dp[i][k] = min(dp[i-1][k-ar[i][j].fi]+ar[i][j].se,dp[i][k]);
}
}
}
int ans = 0;
for(int i = sum; i >= 0; --i) {
if(dp[tot-1][i]<=m) { //找第一个小于等于给定时间的价值
ans = i;
break;
}
}
printf("%d\n", ans);
}
return 0;
} 3.精灵王国
Description
小J离开了神秘群岛之后，来到了繁华的精灵王国。
精灵王国中有n个城市，现在已知第 i 个城市和第 i + 1个城市之间有一条长度为d[i]的双向道路。（特别的，第n个城市和第1个城市之间有一条长度为d[n]的双向道路）。
随着经济的发展，精灵王国的城市之间建立了m条地铁，第i条地铁可以从城市u[i]前往v[i]，也可以从v[i]前往u[i]，同时地铁的长度为w[i]。
现在小J在各个城市之间旅游，小J想知道从城市x前往城市y旅游需要花费多长的时间？
Input
第一行为2个整数n、m。
第二行为n个正整数d[i]。
接下来m行每行三个正整数u[i]、v[i]、w[i]。
第m+3行为一个正整数Q，表示询问次数。
接下来Q行每行两个正整数x、y，表示一次从城市x到城市y的旅行。
数据范围：1<=n,q<=1e5,1<=m<=30,1<=u[i],v[i],x,y<=n,1<=d[i],w[i]<=1e9;
Output
输出Q行每行一个正整数表示该次旅行的最短时间。
Sample Input 1
4 1 1 2 3 6 1 3 2 5 1 2 1 4 1 3 2 3 4 3
Sample Output 1
1 5 2 2 3
看起来挺难的，其实是到原题。。，把数据范围改了一下，见牛客第二场挑战赛。
看起来很难，实际上简单的一匹，只有30条铁路，直接把有铁路的60个点直接全部跑一次最短路，然后问两个点之间的最短距离，要么坐了地铁，那么就是到60个点中的一个最短路加上从这个有铁路的点到另一个点的最短路，要么就是不做地铁，不做地铁一个前缀和就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int n,m;
int d[maxn];
LL dp[maxn];
vector<int> v;
bool u[maxn];
struct edge {
int to,next;
LL w;
} eg[maxn*3];
int tot,head[maxn];
void add(int u,int v,int w) {
eg[tot].to=v;
eg[tot].w=w;
eg[tot].next=head[u];
head[u]=tot++;
}
LL dis[65][maxn];
int main() {
scanf("%d%d",&n,&m);
mem(head,-1);
for(int i = 1; i <= n ; i ++) {
scanf("%d",&d[i]);
dp[i]=dp[i-1]+d[i];
if(i==n) {
add(1,n,d[i]);
add(n,1,d[i]);
} else {
add(i,i+1,d[i]);
add(i+1,i,d[i]);
}
}
while(m--) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(u[a]==0) {
v.push_back(a);
u[a]=1;
}
if(u[b]==0) {
v.push_back(b);
u[b]=1;
}
add(a,b,c);
add(b,a,c);
}
mem(dis,inf);
priority_queue<P,vector<P>,greater<P> > q;
for(int i = 0 ; i < v.size(); i ++) {
dis[i][v[i]]=0;
q.push(P(0,v[i]));
while(q.size()) {
int u = q.top().second;
q.pop();
for(int j = head[u]; j!=-1; j=eg[j].next) {
edge &e=eg[j];
if(dis[i][e.to]>dis[i][u]+e.w) {
dis[i][e.to]=dis[i][u]+e.w;
q.push(P(dis[i][e.to],e.to));
}
}
}
}
int Q;
scanf("%d",&Q);
while(Q--) {
int a,b;
scanf("%d%d",&a,&b);
if(a>b)swap(a,b);
LL ans=min(dp[b-1]-dp[a-1],dp[n]-(dp[b-1]-dp[a-1]));
for(int i =0 ; i <v.size(); i++) {
// debug(dis[i][a]+dis[i][b]);
ans=min(ans,dis[i][a]+dis[i][b]);
}
printf("%lld\n",ans);
}
return 0;
} 5.zzq的数学教室2
Description
zzq想保研，他的成绩单上有一排非递减顺序的成绩，面试时老师想知道他数学成绩的位置，zzq知道他的数学成绩是x分，他要找到第一个出现x的位置。
他想运用二分查找算法， 代码如下：
显然L就是最终的位置。
可是现在他的成绩全被lcy学姐打乱了（随机把数字乱放）。
他想知道最后找到的位置仍然是原来的位置的概率， 请你帮帮他。
概率是在模1e9 + 7意义下的， 即 p / q = p * inv(q) 。inv(q)是q在模1e9 + 7 意义下的逆元。
Input
输入第一行一个正整数N。
第二行N个正整数a[i]，代表的是原来的成绩单，呈非递减顺序。
第三行一个数字x，代表他的数学成绩。
1 <= N <= 1e5
1 <= a[i] <= 1e9
x保证是某一个a[i]。
Output
输出一个整数代表概率。
Sample Input 1
8 1 1 1 3 7 9 9 10 1
Sample Output 1
1
Sample Input 2
3 1 2 2 2
Sample Output 2
333333336
Hint
对于第二个样例，lcy学姐可能打乱成这3种等概率的情况：
1 2 2
2 1 2
2 2 1
其中只有第一种会结果正确。
概率是1 / 3。
题解：水题，直接把小于x的个数，a，和大于x的个数算出来b，然后照这个二分写法一路把答案算下去就行了；具体看代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int l,r;
LL pow(LL x,LL n) {
LL ans=1;
while(n) {
if(n&1)ans=ans*x%mod;
x=x*x%mod;
n>>=1;
}
return ans;
}
int n,x;
int a[maxn];
int main() {
scanf("%d",&n);
for(int i = 1 ; i <= n ; i ++) {
scanf("%d",&a[i]);
}
scanf("%d",&x);
LL mx=0,mi=0;
for(int i = 1; i<=n; i++) {
if(a[i]>=x) {
mx++;//大于等于x的个数
} else {
mi++;//小于等于x的个数
}
}
int l=1,r=n;
LL ans=1;
while(l<=r) {
int mid=(l+r)/2;
if(a[mid]>=x) {
ans=ans*mx%mod*pow(mi+mx,mod-2)%mod;//需要一个选一个大于等于x的数，选到的概率是(mx/(mi+mx));
mx--;
r=mid-1;
} else {
ans=ans*mi%mod*pow(mi+mx,mod-2)%mod;//同上。
mi--;
l=mid+1;
}
}
printf("%lld\n",ans);
return 0;
}
6.zzq的数学教室
Description
众所周知，摸鱼是qwb的一大爱好。即使是在zzq的数学课上，qwb也是在疯狂摸鱼。这被眼尖的zzq发现了，所以zzq决定考考摸鱼的qwb，如果qwb答不出来，他的平时分自然就归零了。
现在zzq把数字1~n从左至右排成一排（第i个数的值为i），接下来进行m***作，每次操作描述如下：将奇数位置的数字取出形成序列A，将偶数位置的数字取出形成序列B，将A序列拼接在B序列之后，构成新的序列。
现在问题来了：进行m次操作后，第k个位置的数字是多少呢？
Input
第一行，输入2个正整数n,q
接下来q行，每行2个整数m和k，表示zzq想知道在m次操作之后第k个位置上的数是多少。
数据范围：
n<=5000
q<=1e6
m<=1e6
k<=n;
Output
输出q行，每行输出第k个位置的数字。
Sample Input 1
5 2 1 2 2 3
Sample Output 1
4 2
水题
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"["<<x<<"]"<<endl;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const int maxn=5e3+7;
const int inf=0x3f3f3f3f;
int n,q;
int ar[maxn], br[maxn];
int ans[maxn][maxn];
int main(){
while(~scanf("%d%d", &n, &q)){
for(int i = 1; i <= n; ++i){
ar[i] = ans[0][i] = i;
}
int tot, tim = 1;
do{
tot = 1;
for(int i = 2; i <= n; i += 2){
ans[tim][tot] = ans[tim-1][i];
//printf("%d ", ans[tim][tot]);
tot++;
}
for(int i = 1; i <= n; i += 2){
ans[tim][tot] = ans[tim-1][i];
//printf("%d ", ans[tim][tot]);
tot++;
}
int flag = 0;
for(int i = 1; i <= n; ++i){
if(ans[tim][i] != ar[i])flag = 1;
}
if(flag == 0)break;
tim ++;
}while(1);
//printf("*%d\n",tim);
int m, k;
while(q--){
scanf("%d%d", &m, &k);
m %= tim;
if(m == 0)m = tim;
printf("%d\n", ans[m][k]);
}
}
return 0;
}
7.玩游戏
Description
dr喜欢玩游戏，现在有n个游戏，每个游戏时间为[Li,Ri)，现在问题是，找出最长的一段游戏时间，使得该时间段被至少k个游戏完全覆盖(这k个区间要每一个都要完全覆盖你选出来的这个区间）。
Input
多组输入
第一行n,k(1<=n,k<1e6)
接下来n行，每行两个数l,r(1<=l<r<=1e9)
Output
输出这个区间的长度
Sample Input 1
3 2 1 5 1 4 1 3
Sample Output 1
3
贪心就好，每次从最先结束的一个线段开始选，然后找最小的k小于当前线段结束点的起点，然后满足条件的区间就是当前区间的终点减去k个起始点中最大值。找完这个线段的终点后把这个区间删掉，然后依次类推下去知道找完所有的线段。本来每次找k个小于当前线段的结束点起始点需要一个操作，但是因为数据有点水，被我水过去了。。。
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"["<<x<<"]"<<endl;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const int maxn=1e6+7;
const int inf=0x3f3f3f3f;
struct th {
int st,en,id;
bool operator <(const th a)const {
if(en==a.en) {
return st<a.st;
} else return en<a.en;
}
} a[maxn];
bool u[maxn];
priority_queue<P,vector<P>,greater<P> >q;
int main() {
int n,m;
while(~scanf("%d%d",&n,&m)) {
for(int i=0; i<n; i++) {
scanf("%d%d",&a[i].st,&a[i].en);
a[i].id=i;
q.push(P(a[i].st,i));
}
sort(a,a+n);
int cnt=0,ans=0,L=0;
memset(u,0,sizeof(u));
for(int i =0; i<n; i++) {
if(!u[a[i].id])cnt++;
u[a[i].id]=1;
L=a[i].st; //本来这是要找最大值的，但是数据有点水，直接就过去了。。。
while(cnt<m&&q.size()) {
if(u[q.top().second]==1) {
q.pop();
continue;
} else if(q.top().first>=a[i].en) {
break;
} else {
cnt++;
u[q.top().second]=1;
L=max(L,q.top().first);
q.pop();
}
}
if(cnt==m) {
ans=max(ans,a[i].en-L);
}
cnt--;
}
while(q.size())q.pop();
printf("%d\n",ans);
}
return 0;
} 9.签到题
Description
“素数就是因子只包含1和它本身的数”zzq如是说道。
现在zzq的数学课下课了，他发现qwb在他的课摸鱼，于是要出一个题考qwb：N！的素因子有多少个？
如果qwb做不出来就要被py交易！但是qwb完全不知道zzq上课讲了什么，于是向从来不摸鱼的你求助了（划重点：这是简单题）。
Input
第一行输入一个整数T（T \leq 10T≤10），表示有T组数据。
每组数据输入站一行，输入一个整数N（N \leq 10^5N≤105）
Output
对于每组数据，输出N!有多少个素因子
Sample Input 1
2 1 4
Sample Output 1
0 4
如题目。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
int prim[maxn], p[maxn], pcnt;
int sum[maxn];
int main() {
int t;
prim[0]=1;
prim[1]=1;
pcnt = 0;
for(int i =2; i < maxn; i++) {
if(!prim[i]) p[pcnt++] = i;
for(int j = 0; j < pcnt&&i*p[j]<maxn; ++j) {
prim[i*p[j]] = 1;
if(i%p[j] == 0)break;
}
}
sum[0] = 0;
sum[1] = 0;
sum[2] = 1;
for(int i = 3; i < maxn; ++i) {
int tmp = i,cnt = 0;
if(prim[i] == 0) {
sum[i]=sum[i-1]+1;
continue;
}
for(int j = 0; j < pcnt; ++j) {
while(tmp % p[j] == 0) {
tmp /= p[j];
cnt++;
}
if(tmp == 1)break;
}
if(tmp!=1)cnt++;
sum[i] = sum[i-1] + cnt;
}
int n;
scanf("%d",&t);
while(t--) {
scanf("%d", &n);
printf("%d\n", sum[n]);
}
return 0;
}
京公网安备 11010502036488号