ZOJ Problem Set - 2965 Accurately Say "CocaCola"! http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2965
打表。求含有7或者是7的倍数的数。题目输入p，输出第一个连续出现p个满足条件的头。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=;
bool vis[M];
bool isgood(int x){
while(x){
if(x%==) return true;
x/=;
}
return false;
}
int ans[M];
int main(){
mt(vis,);
for(int i=;i<M;i++){
if(isgood(i)||!(i%)){
vis[i]=true;
}
}
for(int i=;i<=;i++){
ans[i]=M;
}
int s=,t=;
for(int i=;i<M;i++){
if(!vis[i]){
s=t=i;
}
else{
t++;
ans[t-s]=min(ans[t-s],s+);
}
}
int n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return ;
}
ZOJ Problem Set - 2966 Build The Electric System http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2966
最小生成树 prim
#include<cstdio>
const int inf=0x3f3f3f3f;
class Prim { ///最小生成树(无向图)o(MV^2)要保证图连通
typedef int typec;///边权的类型
static const int MV=;///点的个数
int n,i,j,k,pre[MV];///pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1
bool vis[MV];
typec mat[MV][MV],dist[MV],res;
public:
void init(int tn) { ///传入点数，点下标0开始
n=tn;
for(i=; i<n; i++)
for(j=; j<n; j++)
mat[i][j]=i==j?:inf;///不相邻点边权inf
}
void add(int u,int v,typec w) {
if(mat[u][v]>w) {
mat[u][v]=w;
mat[v][u]=w;
}
}
typec solve() { ///返回最小生成树的长度
for(res=i=; i<n; i++) {
dist[i]=inf;
vis[i]=false;
pre[i]=-;
}
for(dist[j=]=; j<n; j++) {
for(k=-,i=; i<n; i++) {
if(!vis[i]&&(k==-||dist[i]<dist[k])) {
k=i;
}
}
for(vis[k]=true,res+=dist[k],i=; i<n; i++) {
if(!vis[i]&&mat[k][i]<dist[i]) {
dist[i]=mat[pre[i]=k][i];
}
}
}
return res;
}
}gx;
int main(){
int t,n,m,u,v,w;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
gx.init(n);
while(m--){
scanf("%d%d%d",&u,&v,&w);
gx.add(u,v,w);
}
printf("%d\n",gx.solve());
}
return ;
}
Kruskal
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
class Kruskal { ///最小生成树(无向图)o(ME*logME)
typedef int typec;///边权的类型
static const int ME=*;///边的个数
static const int MV=;///点的个数
class UnionFindSet { ///并查集
int par[MV];
public:
void init() {
mt(par,-);
}
int getroot(int x) {
int i=x,j=x,temp;
while(par[i]>=) i=par[i];
while(j!=i) {
temp=par[j];
par[j]=i;
j=temp;
}
return i;
}
bool unite(int x,int y) {
int p=getroot(x);
int q=getroot(y);
if(p==q)return false;
if(par[p]>par[q]) {
par[q]+=par[p];
par[p]=q;
} else {
par[p]+=par[q];
par[q]=p;
}
return true;
}
} f;
struct E {
int u,v;
typec w;
friend bool operator < (E a,E b) {
return a.w<b.w;
}
} e[ME];
int le,num,n;
typec res;
public:
void init(int tn){///传入点的个数
n=tn;
le=res=;
f.init();
num=;
}
void add(int u,int v,typec w) {
e[le].u=u;
e[le].v=v;
e[le].w=w;
le++;
}
typec solve(){///返回-1不连通
sort(e,e+le);
for(int i=; i<le&&num<n; i++) {
if(f.unite(e[i].u,e[i].v)) {
num++;
res+=e[i].w;
}
}
if(num<n) res=-;
return res;
}
}gx;
int main(){
int t,n,m,u,v,w;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
gx.init(n);
while(m--){
scanf("%d%d%d",&u,&v,&w);
gx.add(u,v,w);
}
printf("%d\n",gx.solve());
}
return ;
}
ZOJ Problem Set - 2969 Easy Task http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1968
给式子的系数，求导完输出系数，如果全为零输出零，否则从第一个不为零的开始输出。
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=;
int a[M];
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=n;i>=;i--){
scanf("%d",&a[i]);
}
int id=-;
for(int i=n;i>=;i--){
a[i]*=i;
if(a[i]){
id=max(id,i);
}
}
if(id==-){
puts("");
continue;
}
for(int i=id;i>=;i--){
if(i!=id) printf(" ");
printf("%d",a[i]);
}
puts("");
}
return ;
}
ZOJ Problem Set - 2970 Faster, Higher, Stronger http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1969
f就找最小，其他找最大。
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int main(){
int t,n,a;
scanf("%d",&t);
char op[];
while(t--){
scanf("%s%d",op,&n);
bool sma=false;
int ans=-inf;
if(op[]=='F'){
sma=true;
ans=inf;
}
for(int i=;i<n;i++){
scanf("%d",&a);
if(sma){
ans=min(ans,a);
}
else{
ans=max(ans,a);
}
}
printf("%d\n",ans);
}
return ;
}
ZOJ Problem Set - 2971 Give Me the Number http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1970
3个3个处理，然后加起来。
#include<cstdio>
#include<cstring>
const int M=;
char a[M*M],b[M][M];
int ans[M],val[M];
char gewei[M][M]={"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
char shiwei[M][M]={"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
char jishi[M][M]={"twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
int main(){
int t;
scanf("%d",&t);
getchar();
while(t--){
gets(a);
int cnt=,lb=;
for(int i=;a[i];i++){
if(a[i]==' '){
b[cnt][lb]=;
cnt++;
lb=;
}
else{
b[cnt][lb++]=a[i];
}
}
b[cnt][lb]=;
cnt++;
for(int i=;i<=;i++){
ans[i]=;
val[i]=;
}
int sta=;
for(int i=cnt-;i>=;i--){
if(!strcmp(b[i],"and")) continue;
int now=-;
for(int j=;j<;j++){
if(!strcmp(b[i],gewei[j])){
now=j;
break;
}
}
if(now==-){
for(int j=;j<;j++){
if(!strcmp(b[i],shiwei[j])){
now=j+;
break;
}
}
}
if(now==-){
for(int j=;j<;j++){
if(!strcmp(b[i],jishi[j])){
now=(j+)*;
break;
}
}
}
if(~now){
ans[sta]+=now*val[sta];
}
else{
if(!strcmp(b[i],"hundred")){
val[sta]=;
continue;
}
if(!strcmp(b[i],"thousand")){
sta=;
continue;
}
if(!strcmp(b[i],"million")){
sta=;
continue;
}
}
}
int sum=;
for(int i=;i<=;i++){
sum*=;
sum+=ans[i];
}
printf("%d\n",sum);
}
return ;
}
ZOJ Problem Set - 2972 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1971
dp i j 表示第 i 个位置 还剩 j 的体力 能获得的最小时间，有三种方式转移，根据题目输入来转移。用t1就要浪费f1 用t2不变， 用t3还能挣点体力，注意体力上限m
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int M=;
struct G{
int T1,T2,T3,F1,F2;
}sta[M];
int dp[M][M];
int main(){
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d%d%d%d%d",&sta[i].T1,&sta[i].T2,&sta[i].T3,&sta[i].F1,&sta[i].F2);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
dp[i][j]=inf;
}
}
dp[][m]=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(j>=sta[i+].F1){
dp[i+][j-sta[i+].F1]=min(dp[i+][j-sta[i+].F1],dp[i][j]+sta[i+].T1);
}
dp[i+][j]=min(dp[i+][j],dp[i][j]+sta[i+].T2);
dp[i+][min(m,j+sta[i+].F2)]=min(dp[i+][min(m,j+sta[i+].F2)],dp[i][j]+sta[i+].T3);
}
}
int ans=inf;
for(int j=;j<=m;j++){
ans=min(ans,dp[n][j]);
}
printf("%d\n",ans);
}
return ;
}
ZOJ Problem Set - 2975 Kinds of Fuwas http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1974
求四个角相等的矩形个数。n^3的做法。枚举两列n^2，on枚举这两列有几对一样的，然后他们可以组成C n选2 种矩形。
#include<cstdio>
typedef long long LL;
const int M=;
char a[M][M];
char cp[]={'B','J','H','Y','N'};
int main(){
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%s",a[i]);
}
LL ans=;
for(int k=;k<;k++){
for(int x=;x<m;x++){
for(int y=x+;y<m;y++){
LL sum=;
for(int i=;i<n;i++){
if(cp[k]==a[i][x]&&cp[k]==a[i][y]){
sum++;
}
}
ans+=sum*(sum-)/;
}
}
}
printf("%lld\n",ans);
}
return ;
}
ZOJ Problem Set - 2976 Light Bulbs http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1975
因为是格点，整点，所以200*200枚举点，对每个点枚举灯算总和。4*10^6*case
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int M=;
struct point3 {
double x,y,z,I;
} p[M],now;
double Distance(point3 p1,point3 p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
int main() {
int t,n;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z,&p[i].I);
}
double ans=;
for(int x=-;x<=;x++){
for(int y=-;y<=;y++){
now.x=x;
now.y=y;
now.z=;
double sum=;
for(int i=;i<n;i++){
double dist=Distance(now,p[i]);
sum+=p[i].I*p[i].z/dist/dist/dist;
}
ans=max(ans,sum);
}
}
printf("%.2f\n",ans);
}
return ;
}
end