提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助檔案
文章目錄
- 基本資訊
- 一、奶酪
- 二、時間復雜度
- 三，換教室
- 四，斗地主
基本資訊
題數：4
時間：3.5h
分數：153/400
來源：2017noip
一、奶酪
演算法：BFS寬搜/并查集
估分：100
得分：80
代碼：
#include<bits/stdc++.h>
using namespace std;
struct node{
long long x;
long long y;
long long z;
}a[2005];
long long T,n,h,r,d;
bool p[2005][2005],ch[2005],vis[2005];
int dist(node a,node b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
int main(){
scanf("%d",&T);
for(long long i=1;i<=T;i++){
memset(p,0,sizeof(p));
memset(ch,0,sizeof(ch));
memset(vis,0,sizeof(vis));
queue<int> w;
scanf("%d%d%d",&n,&h,&r);
d=2*r;
for(long long j=1;j<=n;j++){
scanf("%d%d%d",&a[j].x,&a[j].y,&a[j].z);
if(a[j].z+r>=h) ch[j]=1;
if(a[j].z<=r) w.push(j),vis[j]=1;
for(long long k=1;k<=j-1;k++){
if(dist(a[k],a[j])<=d*d) p[j][k]=p[k][j]=1;
}
}
bool flag=1;
while(!w.empty()){
long long temp=w.front();
w.pop();
if(ch[temp]){
flag=0;
cout<<"Yes"<<endl;
break;
}
for(long long y=1;y<=n;y++){
if(p[temp][y]&&!vis[y]){
w.push(y);
vis[y]=1;
}
}
}
if(flag) cout<<"No"<<endl;
}
return 0;
}
正解：
#include <bits/stdc++.h>
using namespace std;
#define maxn 1003
#define ll long long
int n;
ll h,r;
int head[maxn*maxn*2];
struct Edge{
int nt,to;
}edges[maxn*maxn*2];
ll x[maxn],y[maxn],z[maxn];
inline int check(int i,int j)
{
ll xx=(ll)abs(x[i]-x[j])*abs(x[i]-x[j]);
ll yy=(ll)abs(y[i]-y[j])*abs(y[i]-y[j]);
ll zz=(ll)abs(z[i]-z[j])*abs(z[i]-z[j]);
ll rr=(ll)4*r*r;
if ((ll)xx+yy+zz<=rr) return 1;
return 0;
}
int s=0,t=1002;
int b_cnt=0;
inline void addedge(int x,int y)
{
edges[++b_cnt].nt=head[x];
edges[b_cnt].to=y;
head[x]=b_cnt;
}
int vis[maxn];
int main()
{
//freopen("cheese.in","r",stdin);
//freopen("cheese.out","w",stdout);
int T;
scanf("%d",&T);
while (T--)
{
b_cnt=0;
scanf("%d",&n);
scanf("%lld%lld",&h,&r);
for (int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
if (z[i]<=r){ addedge(s,i);}
if (z[i]+r>=h) {
addedge(i,t);
}
}
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
{
if (check(i,j)) {
addedge(i,j);
addedge(j,i);
}
}
vis[s]=1;
vis[t]=0;
queue<int> Q;
Q.push(s);
while (!Q.empty())
{
int u=Q.front();
Q.pop();
//vis[u]=1;
for (int i=head[u];i;i=edges[i].nt)
{
int v=edges[i].to;
if (!vis[v])
{
vis[v]=1;
Q.push(v);
}
}
}
if (!vis[t]) printf("No\n");
else printf("Yes\n");
for (int i=0;i<=b_cnt+1;i++) {
head[i]=0,edges[i].to=0,edges[i].nt=0;
}
for (int i=0;i<=n;i++) vis[i]=0;
}
return 0;
}
二、時間復雜度
演算法：堆疊，dfs深搜，哈希
估分：80
得分：73
代碼：
#include<bits/stdc++.h>
using namespace std;
int t,js,hs;
bool ha[1000005];
char p;
struct node{
int ss;
int ee;
int fa;
int zj;
int tj;
string bl;
int n;
int qq[105];
}f[105];
long long hah(string s){
int ans=0;
for(int i=0;i<s.length();i++)
ans=ans*13+s[i]+1;
return ans;
}
void dfs(int x){
f[x].tj=f[x].zj;
for(int i=1;i<f[x].n;i++){
if(f[f[x].qq[i]].zj!=-1){
dfs(f[x].qq[i]);
f[x].tj=max(f[x].tj,f[x].zj+f[f[x].qq[i]].tj);
}
}
return;
}
int main(){
scanf("%d",&t);
for(int k=1;k<=t;k++){
scanf("%d",&hs);
int tot=0;
bool flag=0;
if(hs%2==1) flag=1;
int now=0;
for(int i=1;i<=4;i++) p=getchar();
if(p=='1'){
js=0;
p=getchar();
p=getchar();
}
else{
p=getchar();
p=getchar();
js=p-'0';
p=getchar();
if(p!=')'){
js=js*10+p-'0';
p=getchar();
}
p=getchar();
}
stack<int> mm;
memset(ha,0,sizeof(ha));
int ans=0;
for(int i=1;i<=hs;i++){
p=getchar();
if(p=='F'){
tot++;
mm.push(i);
cin>>f[i].bl;
if(ha[hah(f[i].bl)]==1) flag=1;
else ha[hah(f[i].bl)]=1;
f[i].fa=now;
f[now].qq[f[now].n++]=i;
now=i;
f[i].n=1;
p=getchar();
p=getchar();
if(p=='n'){
f[i].ss=250;
p=getchar();
}
else{
f[i].ss=p-'0';
p=getchar();
if(p>='0'&&p<='9'){
f[i].ss=f[i].ss*10+p-'0';
p=getchar();
}
}
p=getchar();
if(p=='n'){
f[i].ee=250;
p=getchar();
}
else{
f[i].ee=p-'0';
p=getchar();
if(p>='0'&&p<='9'){
f[i].ee=f[i].ee*10+p-'0';
p=getchar();
}
}
if(f[i].ee-f[i].ss>=100) f[i].zj=1;
if(f[i].ee-f[i].ss<0) f[i].zj=-1;
if(f[i].ee-f[i].ss>=0&&f[i].ee-f[i].ss<100) f[i].zj=0;
}
if(p=='E'){
if(mm.empty()) flag=1;
else{
int temp=mm.top();
ha[hah(f[temp].bl)]=0;
mm.pop();
if(mm.empty()) now=0;
else now=mm.top();
}
p=getchar();
}
}
if(!mm.empty()) flag=1;
if(flag){
cout<<"ERR"<<endl;
continue;
}
for(int i=1;i<=tot;i++){
if(f[i].fa==0&&f[i].zj!=-1){
dfs(i);
ans=max(ans,f[i].tj);
}
}
if(ans==js) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
正解：
#include <bits/stdc++.h>
using namespace std;
int n, top;//定義如上
char line[105], stk[105];
bool noin[105], nc[105], err;
//小明給的數，最大n次方，當前n次方
int inc, res, nd;
int main() {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%s", &n, line);
if(line[2] == '1') inc = 0;
else sscanf(line, "O(n^%d)", &inc);//sscanf好東西
res = nd = top = 0;
err = 0;
while(n--) {
scanf("\n%[^\n]", line);//scanf讀行（還要讀除上一行的換行）
if(err) continue;
if(*line == 'E') {
if(!top) err = 1;//沒有F與這個E匹配
if(nc[top--]) nd--;//退出O(n)回圈（相當于回溯）
} else {
int len = strlen(line);
top++;
for(int i = 1;i < top;i++)
if(stk[i] == line[2]) err = 1;//變數名重名
noin[top] = noin[top - 1]
|| (line[4] == 'n' && line[len - 1] != 'n');//數字可能占1~3位不確定，所以計算len
if(line[len - 1] != 'n' && line[4] != 'n') {
int a, b;
sscanf(line, "%*s%*s%d%d", &a, &b);
if(a > b) noin[top] = 1;
}
if(line[len - 1] == 'n' && line[4] != 'n')
nc[top] = 1, nd++;//復雜度再乘n
else nc[top] = 0;//避免初始化
stk[top] = line[2];
if(!noin[top] && res < nd) res = nd;//如果能進入就可以嘗試更新答案
}
}
if(top) err = 1;//還有F沒有匹配E
if(err) puts("ERR");
else puts(res == inc ? "Yes" : "No");
}
return 0;
}
三，換教室
四，斗地主
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/305326.html
標籤：其他