2019年2月

题目:https://www.luogu.org/problemnew/show/P1378

难点:计算当前圆是否跟之前的圆产生碰撞 可以计算两点距离然后去掉另一个圆的半径则得到当前圆到另一个圆心得距离 (注意判断两圆相交则扩散半径为0 不能为负数)

#include <iostream>
#include <math.h>
#define pi 3.1415926
using namespace std;
int n,X1,X2,Y1,Y2,x[10],y[10],vis[10];
double r[10],res;
double calc(int i){
    double s1=min(abs(x[i]-X1),abs(x[i]-X2));
    double s2=min(abs(y[i]-Y1),abs(y[i]-Y2));
    //距离哪个点最近
    double ans = min(s1,s2);//最近扩散的距离 
    for(int j = 1; j<=n; j++){
        if(i != j && vis[j]){
            double d = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));//两点距离公式 
            ans = min(ans, max(d-r[j], 0.0));//距离-去另一个圆的半径得到当前圆心到另一个圆的边上的距离 取两个的最小值 
        }
    }
    return ans;
}
void dfs(int now, double sum){
    if(now > n){
        res = max(res, sum);
        return;
    }
    for(int i = 1; i<=n; i++){
        if(!vis[i]){
            r[i] = calc(i);//得出半径 
            vis[i] = 1;
            dfs(now+1, sum + r[i] * r[i] * pi);
            vis[i] = 0;
        }
    }
}
int main(int argc, char** argv) {
    cin >> n;
    cin >> X1 >> Y1 >> X2 >> Y2;
    double s;
    s = abs(X1-X2) * abs(Y1-Y2);//长方形面积
    for(int i = 1; i<=n; i++){
        cin >> x[i] >> y[i];
    }
    dfs(1,0);
    cout << int(s-res+0.5);
    return 0;
}

地址:https://www.luogu.org/problemnew/show/P1120

#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int n,mmax,mmin,arr[70],tot,cnt;
void dfs(int res, int sum, int target, int p){
    if(res == 0){//木棍分完了 可直接输出 
        cout << target ;
        exit(0);
    }
    if(sum == target){ //如果相等则所需木棍数-1 
        dfs(res-1, 0, target, mmax);
        return;
    }
    for(int i = p; i>= mmin; i--){//从上一个坐标开始 到最少 
        if(arr[i] && i + sum <= target){ //当前不为空 且 当前的值加上之前积累的不大于目标值则可继续 
            arr[i]--;
            dfs(res, sum+i, target, i); 
            arr[i]++;
            if( sum == 0 || sum + i == target){ //如果之前总数明明加上自己可以的但是却不行 说明这个木棍不能搭 所以直接退出循环 
                break;
            }
        }
    }
}
int main(int argc, char** argv) {
    cin >> n;
    mmin  = n;
    int temp;//桶记录 
    while(n--){
        cin >> temp;
        if(temp <= 50){
            cnt++;
            arr[temp]++;
            tot += temp;
            mmax = max(mmax, temp);
            mmin = min(mmin, temp);
        }
    }
    temp = tot / 2;//最少分两根 最多每段mmax 到 每段tot/2 
    for(int i = mmax; i<=temp; i++){
        if(tot % i == 0){ //优化点1 只有能被整除才能分 
            dfs(tot/i, 0, i, mmax);
        }
    }
    cout << tot;
    return 0;
}

题目:https://www.luogu.org/problemnew/show/P3383

#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define maxn 10000005
#define maxm 100005
int n,m,prime[maxn],check[maxn],tot;
void doPrime(int n){
    check[0] = 1;
    check[1] = 1;
    for(int i = 2; i <= n; i++){
            if(check[i] == 0){
                prime[tot++] = i;
            }
            for(int j = 0; j<tot; j++){
                if(i * prime[j] > n){
                    break;
                }
                check[i*prime[j]] = 1;
                if(i % prime[j] == 0){
                    break;
                }
            }
        }
}
int main(int argc, char** argv) {
    cin >> n >> m;
    doPrime(n);
    for(int i = 1; i<=m; i++){
        int t;
        cin >> t;
        if(check[t] == 0){
            cout << "Yes" << endl;
        }else {
            cout << "No" << endl;
        }
    }
    return 0;
}

题目:https://www.luogu.org/problemnew/show/P4779
题解:https://www.luogu.org/problemnew/solution/P4779
用了priority_queue来实现优先队列 注意此处的比较函数,如果要从小到大排序的话是:

bool operator(const node & b) const {
    return val > b.val; //相反
}
#include <iostream>
#include <queue>
using namespace std;
#define maxn 100010
#define maxm 500010
#define inf 2147483647
int n,m,s,head[maxn],cnt,dis[maxn],vis[maxn];
struct {
    int v,w,next;
}e[maxm];
void add(int u,int v,int w){
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

//堆节点 
struct node
{
    int dis;
    int pos;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};
inline void dijkstra(){
    std::priority_queue<node> q; //优先队列 
    for(int i = 1; i<=n; i++){
        dis[i] = inf;
    }
    q.push(node { 0,s });
    dis[s] = 0;
    while(!q.empty()){
        node tmp = q.top();
        q.pop();
        int u = tmp.pos, d = tmp.dis;
        if(vis[u]){
            continue;
        }
        vis[u] = 1;
        for(int i = head[u]; i; i = e[i].next){
            int v = e[i].v;
            if(dis[v] > dis[u] + e[i].w){
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]){
                    q.push( (node){
                        dis[v],
                        v
                    } );
                }
            }
        }
    }
}
int main(int argc, char** argv) {
    cin >> n >> m >> s;
    for(int i = 1; i<=m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    dijkstra();
    for(int i = 1; i<= n; i++){
        cout << dis[i] << " ";
    }
    return 0;
}

https://www.luogu.org/problemnew/show/P3371
SPFA:https://blog.csdn.net/rentenglong2012/article/details/78483662
SPFA与DJISTRA的区别就在于
SPFA要松弛队列中的点 其中边如果被松弛了的话则继续往下松弛
其中SPFA中的VIS是用来判断指定点是否在优化队列中。

#include <iostream>
#include <queue>
using namespace std;
#define inf 2147483647
#define maxn 10005
#define maxm 500005
queue<int> q;
int n,m,s,a,b,c,cnt,head[maxm],dis[maxn];
bool vis[maxn];
struct {
    int next,v,w;
}e[maxm];
//链式前向星 
void add(int u,int v, int w){
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void spfa(){
    
    for(int i = 1; i<=n; i++){
        dis[i] = inf;
        vis[i] = false;
    }
    q.push(s);
    dis[s] = 0;
    vis[s] = true;
    //找出队列 
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        //出栈 
        for(int i = head[u]; i; i = e[i].next){
            int v = e[i].v;
            if(dis[v] > dis[u] + e[i].w){
                dis[v] = dis[u] + e[i].w;//是否比原来优 
                if(vis[v]){
                    continue;
                }
                vis[v] = true;
                //进栈 
                q.push(v);
            }
        }
    }
}
int main(int argc, char** argv) {
    cin >> n >> m >> s;
    for(int i = 1; i<=m; i++){
        cin >> a >> b >> c;
        add(a,b,c);
    }
    spfa();
    for(int i = 1; i<=n; i++){
        cout << dis[i] << " ";
    }
    return 0;
}