本文主要是介绍Codeforces Gym 101653 - 2014-2015 ACM-ICPC Pacific Northwest Regional Contest (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接
M-Polyhedra
水题
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=100005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);int main() {int t,a,b,ans;scanf("%d",&t);while (t--) {scanf("%d%d",&a,&b);ans=2+b-a;printf("%d\n",ans);}return 0;
}
水
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=1005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
int a[maxn];int main() {int n,i,j,ans,t;scanf("%d",&t);while (t--) {scanf("%d",&n);mem0(a);for (i=1;i<=n;i++) {scanf("%d",&j);a[j]++;}ans=0;a[0]=0;for (i=1;i<=1000;i++) {if (a[i]>a[ans]) ans=i;}printf("%d\n",ans);}return 0;
}水
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=1005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
int a[maxn];
db c[maxn],w[maxn];int main() {int t;scanf("%d",&t);while (t--) {int i,j,ans,n;scanf("%d",&n);mem0(a);ans=0;for (i=1;i<=n;i++) {scanf("%lf%lf",&w[i],&c[i]);a[i]=1;for (j=1;j<i;j++) {if (w[j]<w[i]&&c[j]>c[i]) a[i]=max(a[i],a[j]+1);}ans=max(ans,a[i]);}printf("%d\n",ans);}return 0;
}
R-Ramp Number
数位DP水题
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef unsigned long long ll;
typedef long double ld;
const int maxn=85,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
const ld pi=acos(-1.0L);
ll dp[maxn][11];
int num[maxn];
char s[maxn]; ll dfs(int len,int last,bool HaveLimit) { if (len==0) return 1; if (dp[len][last]!=-1&&!HaveLimit) return dp[len][last]; int p=HaveLimit?num[len]:9,i; ll ans=0;for (i=last;i<=p;i++) { ans+=dfs(len-1,i,HaveLimit&&i==num[len]);
// ans%=mod; } if (!HaveLimit) dp[len][last]=ans; return ans;
} int main() { int cas; scanf("%d",&cas); memset(dp,-1,sizeof(dp)); while (cas--) { scanf("%s",s); int len=strlen(s),i,j,flag=0; for (i=0;i<len;i++) { num[len-i]=s[i]-'0'; if (i>0) if (s[i]<s[i-1]) {flag=1;break;} } if (flag) {printf("-1\n");continue;}ll ans=0; for (j=1;j<=num[len];j++) { ans+=dfs(len-1,j,j==num[len]); // ans%=mod; } for (i=len-1;i>0;i--) { for (j=1;j<=9;j++) { ans+=dfs(i-1,j,0); // ans%=mod; } } printf("%lld\n",ans); } return 0;
} 模拟题，注意?表示的数字不能在输入当中出现
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=15,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
bool v[maxn];int main() {int cas;scanf("%d",&cas);getchar();while (cas--) {char ch,op;ll a,b,c,aq,bq,cq,t,ad,bd,cd,p[3],i;bool la,lb,lc;la=lb=lc=false;aq=bq=cq=1;a=b=c=ad=bd=cd=0;t=1;mem0(v);scanf("%c",&ch);if (ch=='?'&&t==1) la=true,ad++;if (ch=='-') aq=-1; else if (ch!='?') a=ch-'0',t*=10,v[ch-'0']=true;scanf("%c",&ch);while (ch!='+'&&ch!='-'&&ch!='*') {a*=10;ad*=10;if (ch=='?') ad=ad+1; else a=a+ch-'0',v[ch-'0']=true;if (ch=='?'&&t==1) la=true;t*=10;scanf("%c",&ch);}p[0]=t;op=ch;t=1;scanf("%c",&ch);if (ch=='?'&&t==1) lb=true,bd++;if (ch=='-') bq=-1; else if (ch!='?') b=ch-'0',t*=10,v[ch-'0']=true;scanf("%c",&ch);while (ch!='=') {b*=10;bd*=10;if (ch=='?') bd=bd+1; else b+=ch-'0',v[ch-'0']=true;if (ch=='?'&&t==1) lb=true;t*=10;scanf("%c",&ch);}p[1]=t;t=1;scanf("%c",&ch);if (ch=='?'&&t==1) lc=true,cd++;if (ch=='-') cq=-1; else if (ch!='?') c=ch-'0',t*=10,v[ch-'0']=true;scanf("%c",&ch);while ((ch>='0'&&ch<='9')||ch=='?') {c*=10;cd*=10;if (ch=='?') cd=cd+1; else c+=ch-'0',v[ch-'0']=true;if (ch=='?'&&t==1) lc=true;t*=10;scanf("%c",&ch);}p[2]=t;ll ans=inf;for (i=0;i<=9;i++) {if (v[i]) continue;if (i==0) {if (la)if (p[0]>1||aq==-1) continue;if (lb)if (p[1]>1||bq==-1) continue;if (lc)if (p[2]>1||cq==-1) continue;}ll na,nb,nc;na=(a+ad*i)*aq;nb=(b+bd*i)*bq;nc=(c+cd*i)*cq;// cout << na << ' ' << nb << ' ' << nc << endl;if (op=='+') {if (na+nb==nc) ans=min(i,ans);} elseif (op=='-') {if (na-nb==nc) ans=min(i,ans);} elseif (op=='*') {if (na*nb==nc) ans=min(i,ans);}}if (ans==inf) printf("-1\n"); else printf("%lld\n",ans);}return 0;
}每次更新对应的编号最大值即可。
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=1000005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
map<string,int> mp;
bool v[maxn];int main() {int t;scanf("%d",&t);while (t--) {int i,j,n,l,p,k; mp.clear();mem0(v);scanf("%d",&n);string s;for (i=1;i<=n;i++) {cin >> s;mp[s]=i;}l=0;k=0;int cnt=0;for (i=1;i<=n;i++) {cin >> s;p=mp[s];k=max(k,p);l++;if (i==k) {if (cnt) printf(" ");cnt++;printf("%d",l);l=0;}}printf("\n");}return 0;
}W-Wormhole
用floyd一直被卡，赛后听说spfa/dijkstra可以过，流下了泪水。。。
未AC代码:
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=65,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
ld a[maxn][maxn];
ld x[maxn],y[maxn],z[maxn];
map<string,int> mp;ld sqr(ld x) {return x*x;
}int main() {int cas,cntcas=0;scanf("%d",&cas);string s,t;cout << setiosflags(ios::fixed) << setprecision(0);while (cas--) {cntcas++;int n,m,k,i,j,p;mp.clear();scanf("%d",&n);getchar();for (i=1;i<=n;i++) {char c;scanf("%c",&c);s="";while (c!=' ') {s=s+c;scanf("%c",&c);}mp[s]=i;cin >> x[i] >> y[i] >> z[i];a[i][i]=0;for (j=1;j<i;j++) {a[i][j]=a[j][i]=sqrtl(sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j]));}getchar();}scanf("%d",&m);getchar(); for (i=1;i<=m;i++) {getline(cin,s);int p=s.find(" ");t=s.substr(p+1,s.length());s=s.substr(0,p);int ss,tt;ss=mp[s];tt=mp[t];a[ss][tt]=0;}printf("Case %d:\n",cntcas);for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (i==j) continue; for (k=1;k<=n;k++) { if (i==k||j==k) continue; a[j][k]=min(a[j][k],a[j][i]+a[i][k]); } }int q;scanf("%d",&q);getchar();for (i=1;i<=q;i++) {getline(cin,s);int p=s.find(" ");t=s.substr(p+1,s.length());s=s.substr(0,p);int ss,tt;printf("The distance from ");cout << s;printf(" to ");cout << t;ss=mp[s];tt=mp[t];printf(" is ");cout << a[ss][tt];printf(" parsecs.\n");}}return 0;
}
这篇关于Codeforces Gym 101653 - 2014-2015 ACM-ICPC Pacific Northwest Regional Contest (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
