Applications http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5008
string set 专场
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps=1e-;
const int M=;
set<int> A,B;
set<string> xiaosai[];
int defen[]={,,,};
char op[];
struct G{
double val;
string name;
friend bool operator <(const G &a,const G &b){
return a.val>b.val||(fabs(a.val-b.val)<eps&&a.name<b.name);
}
}p[];
int pri[M],mark[M],pricnt;//mark[i]存i的最小因子，素数时mark[i]==i
void sieve_primes() { //筛素数
pricnt=;
mt(mark,);
mark[]=mark[]=;
for(int i=; i<M; i++) {
if(!mark[i]) pri[pricnt++]=mark[i]=i;
for(int j=; pri[j]*i<M; j++) {
mark[i*pri[j]]=pri[j];
if(!(i%pri[j])) break;
}
}
}
int rat[];
int main(){
sieve_primes();
int t,n,m,q,c,tmp,id;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d%d",&n,&m,&q);
A.clear();
while(q--){
scanf("%d",&tmp);
A.insert(tmp);
}
scanf("%d",&q);
B.clear();
while(q--){
scanf("%d",&tmp);
B.insert(tmp);
}
scanf("%d",&q);
for(int i=;i<;i++){
xiaosai[i].clear();
}
while(q--){
scanf("%s%d",op,&id);
xiaosai[id].insert((string)op);
}
for(int i=;i<n;i++){
p[i].val=;
scanf("%s",op);
p[i].name=(string)op;
scanf("%s",op);
for(int j=;j<=;j++){
if(xiaosai[j].count((string)op)){
p[i].val+=defen[j];
break;
}
}
scanf("%s",op);
if(op[]=='F') p[i].val+=;
scanf("%d%d",&q,&c);
while(q--){
scanf("%d",&tmp);
if(A.count(tmp)){
p[i].val+=2.5;
continue;
}
if(B.count(tmp)){
p[i].val+=1.5;
continue;
}
if(mark[tmp]==tmp){
p[i].val+=;
continue;
}
p[i].val+=0.3;
}
for(int j=;j<c;j++){
scanf("%d",&rat[j]);
}
sort(rat,rat+c);
if(c>){
p[i].val+=max(0.0,(rat[c-]-1200.0)/100.0)*1.5;
}
}
sort(p,p+n);
for(int i=;i<m;i++){
cout<<p[i].name;
printf(" %.3f\n",p[i].val);
}
}
}
return ;
}
Break Standard Weight http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5009
set
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
set<int> my;
int solve(int x,int y){
int res=;
for(int i=;i+i<=x;i++){
my.clear();
int a=i,b=x-i,c=y;
my.insert(a);
my.insert(b);
my.insert(c);
my.insert(abs(a+b));
my.insert(abs(a-b));
my.insert(abs(a+c));
my.insert(abs(a-c));
my.insert(abs(b+c));
my.insert(abs(b-c));
my.insert(abs(a+b+c));
my.insert(abs(a+b-c));
my.insert(abs(a-b+c));
my.insert(abs(a-b-c));
my.erase();
int cnt=my.size();
res=max(res,cnt);
}
return res;
}
int main(){
int t,x,y;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d",&x,&y);
printf("%d\n",max(solve(x,y),solve(y,x)));
}
}
return ;
}
Density of Power Network http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5011
set
#include<cstdio>
#include<set>
using namespace std;
const int M=;
struct P{
int x,y;
friend bool operator <(const P &a,const P &b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
}p[M];
set<P> my;
int main(){
int t,n,m;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<m;i++){
scanf("%d",&p[i].x);
}
for(int i=;i<m;i++){
scanf("%d",&p[i].y);
}
my.clear();
for(int i=;i<m;i++){
if(p[i].x>p[i].y) swap(p[i].x,p[i].y);
my.insert(p[i]);
}
printf("%.3f\n",my.size()*1.0/n);
}
}
return ;
}
Friends http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5013
暴力加边
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
const int M=;
bool mat[M][M];
void add(int u,int v){
mat[u][v]=mat[v][u]=true;
}
int main(){
int t,n,m,K,u,v;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d%d",&n,&m,&K);
mt(mat,);
while(m--){
scanf("%d%d",&u,&v);
add(u,v);
}
int ans=;
bool flag=true;
while(flag){
flag=false;
for(int i=;i<n;i++){
for(int j=i+;j<n;j++){
if(!mat[i][j]){
int sum=;
for(int k=;k<n;k++){
if(k!=i&&k!=j&&mat[i][k]&&mat[k][j]){
sum++;
}
}
if(sum>=K){
ans++;
flag=true;
add(i,j);
}
}
}
}
}
printf("%d\n",ans);
}
}
return ;
}
Hard to Play http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5015
求最大最小值
#include<cstdio>
int solve(int point,int times,int &combo){
int res=;
for(int i=;i<times;i++,combo++){
res+=point*(combo*+);
}
return res;
}
int main(){
int t,a,b,c,combo,big,sma;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d%d",&a,&b,&c);
combo=sma=;
sma+=solve(,a,combo);
sma+=solve(,b,combo);
sma+=solve(,c,combo);
combo=big=;
big+=solve(,c,combo);
big+=solve(,b,combo);
big+=solve(,a,combo);
printf("%d %d\n",sma,big);
}
}
return ;
}
In 7-bit http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5016
注意la==0
#include<cstdio>
#include<cstring>
const int M=;
char a[M];
int main(){
int t;
while(~scanf("%d",&t)){
getchar();
while(t--){
gets(a);
int la=strlen(a);
if(la==){
puts("");
continue;
}
int len=la;
while(len>){
int now=len%;
len/=;
if(len) now|=;
printf("%02X",now);
}
for(int i=;i<la;i++){
printf("%02X",a[i]);
}
puts("");
}
}
return ;
}
Java Beans http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5017
n个人坐成环，求连续m个和最大
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=;
int a[M];
int main(){
int t,n,m;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
int ans=;
for(int i=;i<n;i++){
int sum=;
for(int j=;j<m;j++){
sum+=a[i+j];
}
ans=max(ans,sum);
}
printf("%d\n",ans);
}
}
return ;
}
end