1003 Rotation Lock Puzzle
找出每一圈中的最大值即可
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
ll a[][],b[];
vector<ll>q;
int main(){
int i,j,k,m,n;
while(scanf("%d",&n)&&n){
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%I64d",&a[i][j]);
ll ans=a[n/+][n/+];
int num=;
m=n-;
for(k=;k<=n/;k++){
memset(b,,sizeof(b));
q.clear();
for(i=j=k;j<=n-k+;j++)
q.push_back(a[i][j]);
for(j--,i++;i<=n-k+;i++)
q.push_back(a[i][j]);
for(i--,j--;j>=k;j--)
q.push_back(a[i][j]);
for(i--,j++;i>k;i--)
q.push_back(a[i][j]);
for(i=;i<q.size();i++){
b[i%m]+=q[i];
}
ll sum=-;
int num1=;
for(i=;i<m;i++){
if(b[i]>sum){
sum=b[i];
if(m-i<i) num1=m-i;
else num1=i;
}
if(b[i]==sum){
if(m-i<num1) num1=m-i;
else if(i<num1) num1=i;
}
}
ans+=sum;
num+=num1;
m-=;
}
printf("%I64d %d\n",ans,num);
}
return ;
}
1005 Balls Rearrangement
多校联合的原题
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<stdlib.h>
#define ll __int64
using namespace std;
ll gcd(ll a,ll b){
ll t;
if(a<b) swap(a,b);
while(b){
t=a;
a=b;
b=t%b;
}
return a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
ll cal(ll n,ll a,ll b){
ll ans=;
ll temp=;
ll x=,y=,i=;
while (i<n){
temp = min(a-x,b-y);
if (i+temp>n) temp=n-i;
ans += temp*abs(x-y);
x = (x+temp)%a;
y = (y+temp)%b;
i += temp;
}
return ans;
}
int main(){
int t;
ll n,a,b,c,ans;
cin>>t;
while (t--){
scanf("%I64d%I64d%I64d",&n,&a,&b);
if(a==b){
cout<<<<endl;
continue;
}
c=lcm(a,b);
if (c>=n) ans = cal(n,a,b);
else ans = cal(c,a,b)*(n/c)+cal(n%c,a,b);
printf("%I64d\n",ans);
}
return ;
}
1007 Hamming Distance
随机选取2个点即可，坑……
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
char str[][];
int fun(char a)
{
if(a>='A'&&a<='Z') return a-'A'+;
return a-'';
}
int cal(char a[],char b[])
{
int num=;
for(int i=;i<;i++){
int s=fun(a[i]);
int p=fun(b[i]);
for(int j=;j<;j++){
num+=(s%!=p%);
s/=;
p/=;
}
}
return num;
}
int main(){
int t,i,j,k,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=;i<n;i++){
scanf("%s",&str[i]);
}
int num=;
for(i=;i<=;i++){
j=rand()%n;
k=rand()%n;
while(j==k) k=rand()%n;
int a=cal(str[j],str[k]);
if(a<num) num=a;
}
printf("%d\n",num);
}
return ;
}
1008 Permutation
这题和hdu 3092一样，只不过这题要求路径。
大致思路用筛法求质数，当尽可能是质数时LCM最大，转化为背包问题求。
代码如下：
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define M 10005
using namespace std;
double dp[M];
vector<int> p[M];
int prime[M],cnt,n;
bool f[M];
void init()
{
cnt=;
for(int i=;i<M;i++){
if(!f[i]) prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
}
void solve()
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) p[i].clear();
for(int i=;i<cnt&&prime[i]<=n;i++){
double t=log(prime[i]);
for(int j=n;j>=prime[i];j--){
for(int k=prime[i],num=;k<=j;k*=prime[i],num++)
if(dp[j-k]+t*num>dp[j]){
dp[j]=dp[j-k]+t*num;
p[j]=p[j-k];
p[j].push_back(k);
}
}
}
}
int main()
{
int t,sum;
init();
scanf("%d",&t);
while(t--){
scanf("%d",&n);
solve();
sum=;
for(int i=;i<p[n].size();i++) sum+=p[n][i];
sum=n-sum;
while(sum--) p[n].push_back();
int s=;
sort(p[n].begin(),p[n].end());
for(int i=;i<p[n].size();i++){
int temp=s++;
for(int j=;j<p[n][i];j++)
printf("%d ",s++);
if(i==p[n].size()-) printf("%d\n",temp);
else printf("%d ",temp);
}
}
return ;
}
1010 Difference Between Primes
注意细节就可以了
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
bool f[];
int prime[],cnt;
void init()
{
cnt=;
f[]=;
for(int i=;i<=;i++){
if(f[i]==) prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<=;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
}
int main(){
init();
int i,t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
bool flag=;
for(i=;i<cnt;i++){
if(prime[i]+n>&&f[prime[i]+n]==){
flag=;
break;
}
}
if(flag) printf("%d %d\n",prime[i]+n,prime[i]);
else puts("FAIL");
}
return ;
}