洛谷春季 ACM 多校训练第一周

T122399 Goldbach's conjecture

题意:给你n,让你证明哥德巴赫猜想,1e9复杂度;

这题复杂度怎么算都不对,线性筛数组开不了这么大,
然后惊讶的暴力居然过了。
证法如下:

 log(n)实在很快呀,1e9也就30左右,这样算就对了;

#include<bits/stdc++.h>
using namespace std;
bool isprime(int x){
    for(int i=2;i*i<=x;i++){
    if(x%i==0)return 0;
    }
    return 1;
}
int main(){
    int n;
    cin>>n;
    for(int i=2;i*i<n;i++){
    if(isprime(i)&&isprime(n-i)){
    cout<<i<<" "<<n-i<<endl;
    break;
    }
    }


    return 0;
}
View Code

T122397 Everybody deserves a long long name

这题没水平;
不说了;

T122394 Billionaire

题意:就是问你多少天能变成亿万富翁,输出日期。

解法:二分出天数,然后用 zeller公式求日期;

这里我卡了一会,就是二分的时候,最大的区间是不能瞎选的,想想也明白,我一开始取很大,他就直接跳过正确答案了,

所以r要是sqrt(2e9),解方程得来;

二分虽然快,但你区间不能选大了,不然答案就不对了,L小了,R大了,都会跳过正确答案,

#include<bits/stdc++.h>
using namespace std;
int getId(int y, int m, int d) {
    if (m < 3) {y --; m += 12;}
    return 365 * y + y / 4 - y / 100 + y / 400 + (153 * (m - 3) + 2) / 5 + d - 307;
}
vector<int> date(int id) {
    int x = id + 1789995, n, i, j, y, m, d;
    n = 4 * x / 146097;
    x -= (146097 * n + 3) / 4;
    i = (4000 * (x + 1)) / 1461001; x -= 1461 * i / 4 - 31;
    j = 80 * x / 2447; d = x - 2447 * j / 80; x = j / 11;
    m = j + 2 - 12 * x; y = 100 * (n - 49) + i + x;
    vector<int>v;
    v.push_back(y),v.push_back(m),v.push_back(d);
    return v;
}
int m;
const int maxn=1000000000;
bool check(int x){
    int sum=m+x*(x+1)/2;
    if(sum>=maxn)return 1;
    else return 0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
    int ty,tm,td;
    scanf("%d %d %d %d",&m,&ty,&tm,&td);
    int id=getId(ty,tm,td);
    int l=0,r=sqrt(2e9);
    while(l<=r){
    int mid=(r+l)/2;
    if(check(mid))r=mid-1;
    else l=mid+1;
    }
    id+=l;
    vector<int>ans=date(id);
    printf("%d %d %d
",ans[0],ans[1],ans[2]);
    }
    // system("pause");
    return 0;
}
View Code

T122398 Final Spark

这题有点锅,但讲了这样一个问题:

 就是说发射一道光波,问你这个人被射中的概率。这个人半径r,跳的半径s,光波宽度w,距离d,

距离d没用,问题转化为w+2r的光波怎么切圆,覆盖面积最大。可以证明切圆时覆盖最大,求导可得;

题有锅,待补;

T122393 À la Volonté du Peuple

题意:就是给你一张图,从1点火,两团火碰在一起会炸,问你能炸多少个。

解法:这题 想了很久也没想出来,还是套路太少。

就是要么在点上炸,要么在边上炸,如果在点上炸,说明,他的最短路上有两个前驱,如果在边上炸,说明他不在最短路上,可以想象有两个人在走,在更新最短路时碰撞,然后炸了。

那问题就是如何判断点有两个前驱,以及一个边不在最短路上。

dijkstra求最短路,然后遍历一遍,如果这个点有两个以上最短路前驱,ans++,如果这个边不在最短路上

ans++,而且你要判重一下,一个边不能判两次。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int maxn=3e5+5;
struct edge{int v,w;edge(int a,int b){v=a,w=b;}};//v终点,w边权
struct node{
    int id,dis;//id点编号 dis暂时距离
    node(int a,int b){id=a,dis=b;}
    friend bool operator<(node a,node b){
    return a.dis>b.dis;//每次让距离小出队
    }
};
vector<edge>e[maxn];
int dis[maxn];//记录最短路
bool done[maxn];//记录是否找到最短路
    int n,m;
void dijkstra(){
    int s=1;//s起点 根据情况改
    for(int i=0;i<=n;i++)dis[i]=inf,done[i]=0;
    dis[s]=0;
    priority_queue<node>Q;
    Q.push(node(s,0));
    while(!Q.empty()){
    node u=Q.top();Q.pop();
    if(done[u.id])continue;
    done[u.id]=1;
    for(int i=0;i<e[u.id].size();i++){//遍历邻居
    edge y=e[u.id][i];
    if(done[y.v])continue;
    if(dis[y.v]>y.w+dis[u.id]){
    dis[y.v]=y.w+u.dis;
    Q.push(node(y.v,dis[y.v]));//更新最短路
    }
    }
    }
}
int main(){

    cin>>n>>m;
    while(m--){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    e[a].pb(edge(b,c));
    if(a!=b)e[b].pb(edge(a,c));
    }
    dijkstra();
    int ans=0,cnt;
    for(int i=1;i<=n;i++){
        cnt=0;
    for(int j=0;j<e[i].size();j++){
    int y=e[i][j].v;
    if(dis[i]==dis[y]+e[i][j].w)cnt++;
    if(i>=y&&dis[i]<dis[y]+e[i][j].w&&dis[y]<dis[i]+e[i][j].w)ans++;
    }
    if(cnt>1)ans++;
    }
    cout<<ans<<endl;
    return 0;
}
View Code

T122395 Counting K-ary Palindromes

k进制,学了再补。

T122396 Deceiver

学了再补。

T122400 Hazardous

线段树合并,学了再补

待更新;

想的太多,做的太少;
原文地址:https://www.cnblogs.com/littlerita/p/12387310.html