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分