202009-01 检测点推荐 源代码丢了 100/100

202009-02 密切接触人群 源代码丢了 100/100

202009-03 点亮数字人生 图论的题目

#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;

int read() {
  int x = 0, f = 1;
  int ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (int)(ch - '0');
    ch = getchar();
  }
  return x * f;
}
const int MAXV = 510;
int G[MAXV][MAXV] = {0};//邻接矩阵
int w[MAXV];//边权重
bool inq[MAXV] = {false};//是否访问过
bool initV[MAXV] = {false};//是否初始化过边
int inDegree[MAXV] = {0};//入度
int outDegree[MAXV] = {0};//出度（未使用）
std::string type[MAXV]; //器件类型
std::vector<int> testInput[10010];//测试输入
std::vector<int> testOutput[10010];//测试输出

bool TopologicalSort(int n, int m){
    //
    //拓扑排序
    int num = 0;
    std::queue<int> q;
    int tempInDegree[MAXV];//临时存储入度
    memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数
    //防止更改全局变量导致问题
    for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队
        if(tempInDegree[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
    //直到队列里没元素为止
        int u = q.front();
        //取出第一个元素
        q.pop();
        for(int i = 0; i < m + n;i++){
            if(inq[i] == false && G[u][i] != 0){
                //入度不为0,而且从u到i有元素
                tempInDegree[i]--;
                //
                if(tempInDegree[i] == 0){
                    //入度减1后元素入度为0,可以放进去
                    q.push(i);
                    inq[i] = true;//i被入度为0了,减不了了
                }
            }
        }
        num++;//这是一个入度为0的元素,处理完毕了!
    }
    if(num == n + m) return true;//可以生成拓扑排序序列
    else return false;
}
//计算值
void calculateValue(int n, int m){

    std::queue<int> q;
    int tempInDegree[MAXV];//临时存储入度
    memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数
    for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队
        if(tempInDegree[i] == 0){
            q.push(i);
        }
    }
    //利用队列进行深度优先遍历
    while(!q.empty()){
        int u = q.front();//起始点
        q.pop();

        for(int i = 0; i < m + n;i++){
            if(inq[i] == false && G[u][i] != 0){
                tempInDegree[i]--;
        //有链接
                if(initV[i] == false){//之前没有被访问过
                    w[i] = w[u];//赋予初始值
                    if(type[i] == "NOT"){//最多或者最少都只有一个输入
                        w[i] = (!w[i]);
                    }
                    initV[i] = true;
                }
                else{
                    //一个一个对输入进行处理
                    if(type[i] == "AND" || type[i] == "NAND"){//有n个输入的
                        w[i] &= w[u];
                    }else if(type[i] == "OR" || type[i] == "NOR"){
                        w[i] |= w[u];
                    }else if(type[i] == "XOR"){
                        w[i] ^= w[u];
                    }
                }

                if(tempInDegree[i] == 0){//入度为零，以它为终点的边数为0
                    if(type[i] == "NAND" || type[i] == "NOR"){
                        w[i] = (!w[i]);
                    }//NAND和NOR的话,要把最后结果置反
                    q.push(i);
                    inq[i] = true;
                    //i这个结点算是遍历好了
                }
            }
        }
    }

}

int main(){
    int q, m, n;
    //输入q和m,n
    scanf("%d", &q);
    while(q--){//问题个数
        //初始化
        std::fill(G[0], G[0] + MAXV*MAXV, 0);
        memset(inDegree, 0, sizeof(inDegree));
        memset(outDegree, 0, sizeof(outDegree));
        //入度和出度为0
        std::fill(inq, inq + MAXV, false);
        std::fill(initV, initV + MAXV, false);
        //点和边的初始化为全部为NO
        for(int i = 0;i < MAXV;i++){
            type[i].clear();
        }
        for(int i = 0;i < 10010;i++){
            for(std::vector<int>::iterator j = testInput[i].begin();j != testInput[i].end();){
                j = testInput[i].erase(j);
            }
        }

        for(int i = 0;i < 10010;i++){
            for(std::vector<int>::iterator j = testOutput[i].begin();j != testOutput[i].end();){
                j = testOutput[i].erase(j);
            }
        }
        //测试输入输出清空
        scanf("%d%d", &m, &n);//输入个数，器件个数
        for(int num = m;num < n + m;num++){
            std::string FUNC;//器件描述
            int k;
            std::cin>>FUNC;
            type[num] = FUNC;

            scanf("%d", &k);
            for(int i = 0;i < k;i++){
                std::string L;
                std::cin>>L;
                int startPoint = std::atoi(L.substr(1, L.length() - 1).c_str()) - 1;//计算起始点编号
                if(L[0] != 'I'){//如果是输出点，则加上输入点的偏移
                    startPoint += m;//加上输入的个数,每个器件有每个器件的输入
                }
                G[startPoint][num] = 1;//把边放进去
                outDegree[startPoint]++;//计算出度
                inDegree[num]++;//计算入度
            }
        }
        //输入储存的数据
        int s;
        scanf("%d", &s);
        for(int i = 0;i < s;i++){//输入数据
            for(int j = 0;j < m;j++){
                int input;
                scanf("%d", &input);
                testInput[i].push_back(input);
            }
        }
        //把输入的数据存进去(是s*j的矩阵)
        for(int i = 0;i < s;i++){//输出数据
            int OutNum;
            scanf("%d", &OutNum);//储存输出的元素
            while(OutNum--){
                int output;
                scanf("%d", &output);
                output = output + m - 1;//加入偏移量
                testOutput[i].push_back(output);
            }
        }

        if(TopologicalSort(n, m) == false){
            printf("LOOP\n");//有环,输出LOOP
        }else{
            for(int i = 0;i < s;i++){
                memset(w, 0, sizeof(w));
                std::fill(inq, inq + 510, false);
                std::fill(initV, initV + MAXV, false);
                for(int j = 0;j < testInput[i].size();j++){
                    w[j] = testInput[i][j];
                }
                //首先把输入存进去
                calculateValue(n, m);
                //一个一个输出结果
                for(int j = 0; j < testOutput[i].size();j++){
                    if(j != 0) printf(" ");
                    printf("%d", w[testOutput[i][j]]);//输出要计算的值
                }
                printf("\n");

            }
        }
    }//q

    return 0;
}

202009-04 星际迷航 100/100

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include <iostream>
using namespace std;
const int N = 100 + 5;
const int M = 2000 + 5;
double o[105], r;
double point[2005][105], result[2005][2005];
double d[2005], rd[2005];//到黑洞距离和切线长度
int read() {
    int x = 0, f = 1;
    int ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (int)(ch - '0');
        ch = getchar();
    }
    return x * f;
}

int main()
{
    int n, m;

    n = read();
    m = read();
    r = read();
    for (int i = 1; i <= n; i++)
        o[i] = read();
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            point[i][j] = read();
    for (int i = 1; i <= m; i++)
    {
        double temp = 0;
        for (int j = 1; j <= n; j++)
        {
            temp += (point[i][j] - o[j]) * (point[i][j] - o[j]);
        }
        d[i] = sqrt(temp);
        rd[i] = sqrt(d[i] * d[i] - r * r);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = i + 1; j <= m; j++)
        {
            double temp = 0;
            for (int k = 1; k <= n; k++)
                temp += (point[i][k] - point[j][k]) * (point[i][k] - point[j][k]);
            double x = sqrt(temp);
            double p = (d[i] + d[j] + x) / 2;
            double s = sqrt(p * (p - x) * (p - d[i]) * (p - d[j]));//海伦-秦九韶公式
            double h = 2 * s / x;//h是垂直平分线长度
            if (h >= r || (x * x + d[i] * d[i] <= d[j] * d[j]) || (x * x + d[j] * d[j] <= d[i] * d[i]))
            {
                result[i][j] = result[j][i] = x;
                continue;
            }
            double angle1 = acos((d[i] * d[i] + d[j] * d[j] - x * x) / (2 * d[i] * d[j]));
            double angle2 = acos(r / d[i]);
            double angle3 = acos(r / d[j]);
            result[i][j] = result[j][i] = (angle1 - angle2 - angle3) * r + rd[i] + rd[j];
        }
    }
    for (int i = 1; i <= m; i++)
    {
        double sum = 0;
        for (int j = 1; j <= m; j++)
        {
            if (i == j) continue;
            sum += result[i][j];
        }
        printf("%.14f\n", sum);
    }
    return 0;
}

n维也不用怕.各种各样的距离求和本质上就是向量点积,面积可以用行列式的性质求出面积,当然它不需要我们求出向量本身,那我们可以用秦九韶公式求面积,也可以求角度用正弦公式

202006-03 Markdown渲染器 100/100(抄的,我做不了满分)

ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);这个语句可以很好的保持效率

#include <iostream>
#include <vector>
using namespace std;

struct Markdown{
    int type;//标记相应的类型 0 空行，1 项目列表第一行 2项目列表其余行 3段落
    string s;
};
//存储每一行
bool isSpace(string s){//判断是否为空行
    for(int i=0;i<s.size();++i)
    {
        if(s[i]!=' ')
        return false;
     }
     return true;
}

string remove_space(string s){//去除首尾的空格
    int pos1=0,pos2=s.length()-1;
    for(int i=0;i<s.length();++i){
        if(s[i]!=' '){
            pos1 =i;
            break;
        }
    }
//从前往后更改
    for(int i=s.length()-1;i>=0;i--){
        if(s[i]!=' '){
            pos2=i;
            break;
        }
    }
//从后往前更改
    string temp =s.substr(pos1,pos2-pos1+1);
//返回去除了空行的子串
    return temp;
}
vector<Markdown> vec;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//保证cin和cout的效率
    Markdown temp;
//保存每一行
    int w,flag=0;//flag标记当前输入行的前一行类型
    string str;
    cin>>w;
    while(getline(cin,str))
    {
//将元素通过cin存进str(按行存储)
        if(isSpace(str)){//处理空行
            if(flag){//上一行不是空行，就添加一个空行
                temp.s="";
                temp.type=0;
                vec.push_back(temp);
                flag=0;
            }
            continue;
        }
//空行,直接放一个flag为0的元素进去
        if(str.size()>=2 && str[0]=='*' && str[1]==' '){
//处理项目列表的第一行
            if(flag==3){//上一行是一个段落，就插入一行空行隔开
                temp.s="";
                temp.type=0;
                vec.push_back(temp);
            }
            //把项目列表第一行再放入vec中
           
            temp.type=1;temp.s=remove_space(str.substr(2,str.size()));
            vec.push_back(temp);
            flag=1;
//注意放的时候要把前面的*_去掉
        }
        else if(str.size()>=2 && str[0]==' ' && str[1]==' '    &&(flag==1 || flag==2)){
//上一个是项目
            if(vec[vec.size()-1].s==""){//项目列表第一行为空
                vec[vec.size()-1].s = remove_space(str);
            }
//第一行为空的话就从这一行开始算
            else
            {
                vec[vec.size()-1].s =vec[vec.size()-1].s+" "+remove_space(str);
//把这一行加进去
            }
            flag=2;
        }
        else{//处理段落
            if(flag==1 || flag==2){
                temp.s="";
                temp.type=0;
                vec.push_back(temp);
                temp.s=remove_space(str);
                temp.type=3;
                vec.push_back(temp);
//上面的是项目的话,之间加一个空行
            }else if(flag ==3){
                vec[vec.size()-1].s = vec[vec.size()-1].s+" " +remove_space(str);
//上面那一行是项目的话就继续加进去
            }
            else{
                temp.s = remove_space(str);
                temp.type = 3;
                vec.push_back(temp);
            }
//前面是空段落
            flag=3;
        }
    }
//下面开始处理
        long long int ans=0;
        for(int i=0;i<vec.size();++i){
            int type =vec[i].type;
            string s=vec[i].s;
//取出来元素
            if(!type) {
            ans++;
            //cout<<endl;//空行
            }
            else if(type ==1 ||type ==2){//项目列表
                if(!s.size()){
                    ans++;
                    continue;
                }
                int t=0;
                while(t<s.size()){
//处理行
                    while(1){//保证每行的开头不是空格
                    if(t>=s.size()) break;
                    if(s[t]!=' ')break;
                    t++;
                    }
                    //cout<<s.substr(t,w-3)<<endl;
                    t+=(w-3);
//把空格算进去
                    ans++;
                }
            }
            else{
//处理段落
                int t=0;
                while(t<s.size()){
                    while(1){//保证每行的开头不是空格
                    if(t>=s.size()) break;
                    if(s[t]!=' ')break;
                    t++;
                    }
                    //cout<<s.substr(t,w)<<endl;
                    t+=w;
                    ans++;
            }
        }
    }
    if(!vec[vec.size()-1].type)
//最后一行是空行
    ans--;
    cout<<ans<<endl;
    return 0;
}

202006-04 1246
我只能做32分