题目1 : 2月29日
描述
给定两个日期，计算这两个日期之间有多少个2月29日（包括起始日期）。
只有闰年有2月29日，满足以下一个条件的年份为闰年：
1. 年份能被4整除但不能被100整除
2. 年份能被400整除
输入
第一行为一个整数T，表示数据组数。
之 后每组数据包含两行。每一行格式为"month day, year"，表示一个日期。month为{"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"}中的一个字符串。day与year为两个数字。
数据保证给定的日期合法且第一个日期早于或等于第二个日期。
输出
对于每组数据输出一行，形如"Case #X: Y"。X为数据组数，从1开始，Y为答案。
数据范围
1 ≤ T ≤ 550
小数据：
2000 ≤ year ≤ 3000
大数据：
2000 ≤ year ≤ 2×109
- 样例输入
-
4 January 12, 2012 March 19, 2012 August 12, 2899 August 12, 2901 August 12, 2000 August 12, 2005 February 29, 2004 February 29, 2012
- 样例输出
-
Case #1: 1 Case #2: 0 Case #3: 1 Case #4: 3
O(1)算法
#include <cstdio> #include <cstdlib> #include <iostream> #include <map> #include <vector> #include <string> #include <algorithm> #include <iosfwd> #include <queue> #include <sstream> #include <stack> #include <cstring> #include <climits> using namespace std; #define LL long long char month[12][20]={"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"}; map<string,int> mp; int main(){ int t,d,y,ans,m; char ms[20]; for(int i=0;i<12;i++){ mp[month[i]]=i+1; } scanf("%d",&t); for(int ks=1;ks<=t;ks++){ scanf("%s %d, %d",ms,&d,&y); m=mp[ms]; ans=y/4;ans-=y/100; ans+=y/400; if((y%4==0&&y%100!=0)||(y%400==0)){ if(m<2)ans--; if(m==2&&d<=29)ans--; } ans=-ans; scanf("%s %d, %d",ms,&d,&y); m=mp[ms]; ans+=y/4;ans-=y/100; ans+=y/400; if((y%4==0&&y%100!=0)||(y%400==0)){ if(m<2)ans--; if(m==2&&d<29)ans--; } printf("Case #%d: %d\n",ks,ans); } return 0; }
题目2 : 回文字符序列
描述
给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中，回文子序列为"a", "a", "aa", "b", "aba"，共5个。内容相同位置不同的子序列算不同的子序列。
输入
第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。
输出
对于每组数据输出一行，格式为"Case #X: Y"，X代表数据编号（从1开始），Y为答案。答案对100007取模。
数据范围
1 ≤ T ≤ 30
小数据
字符串长度 ≤ 25
大数据
字符串长度 ≤ 1000
- 样例输入
-
5 aba abcbaddabcba 12111112351121 ccccccc fdadfa
- 样例输出
-
Case #1: 5 Case #2: 277 Case #3: 1333 Case #4: 127 Case #5: 17
O(n2）的算法#include <cstdio> #include <cstdlib> #include <iostream> #include <map> #include <vector> #include <string> #include <algorithm> #include <iosfwd> #include <queue> #include <sstream> #include <stack> #include <cstring> #include <climits> using namespace std; #define LL long long int mod = 100007; char s[1010]; int dp[1010][1010]; inline void addt(int &a,int x){ a+=x; if(a>=mod)a%=mod; } int solve(){ int n=strlen(s); // memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) for(int j=0;j<n;j++)dp[i][j]=0; for(int i=0;i<n;i++){ dp[i][i]=1; int t=1; if(i+1<n&&s[i]==s[i+1])addt(dp[i+1][i],1); for(int j=i-1;j>=0;j--){ if(s[i]==s[j]){ addt(dp[j][i],dp[j+1][i-1]+dp[j][i-1]+t+(j+1<=i-1)); addt(t,dp[j+1][i-1]+(j+1<=i-1)); }else{ addt(dp[j][i],dp[j][i-1]+t); } } } return dp[0][n-1]; } int main(){ int t; scanf("%d",&t); for(int ks=1;ks<=t;ks++){ scanf("%s",s); printf("Case #%d: %d\n",ks,solve()); } return 0; }
题目3 : 基站选址
时间限制:2000ms单点时限:1000ms内存限制:256MB描述
需要在一个N × M的网格中建立一个通讯基站，通讯基站仅必须建立在格点上。
网格中有A个用户，每个用户的通讯代价是用户到基站欧几里得距离的平方。
网格中还有B个通讯公司，维护基站的代价是基站到最近的一个通讯公司的路程（路程定义为曼哈顿距离）。
在网格中建立基站的总代价是用户通讯代价的总和加上维护基站的代价，最小总代价。
输入
第一行为一个整数T，表示数据组数。
每组数据第一行为四个整数：N, M, A, B。
接下来的A+B行每行两个整数x, y，代表一个坐标，前A行表示各用户的坐标，后B行表示各通讯公司的坐标。
输出
对于每组数据输出一行"Case #X: Y"，X代表数据编号（从1开始），Y代表所求最小代价。
数据范围
1 ≤ T ≤ 20
1 ≤ x ≤ N
1 ≤ y ≤ M
1 ≤ B ≤ 100
小数据
1 ≤ N, M ≤ 100
1 ≤ A ≤ 100
大数据
1 ≤ N, M ≤ 107
1 ≤ A ≤ 1000
- 样例输入
-
2 3 3 4 1 1 2 2 1 2 3 3 2 2 2 4 4 4 2 1 2 2 4 3 1 4 3 1 4 1 3
- 样例输出
-
Case #1: 4 Case #2: 13
O(A+B)的算法#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
#define LL long long
int n,m,a,b;
LL pax,pay,sax,say;
const LL INF = (1uLL<<63)-1;
int main(){
int T;
scanf("%d",&T);
for(int ks=1;ks<=T;ks++){
scanf("%d%d%d%d",&n,&m,&a,&b);
pax=0,sax=0,pay=0,say=0;
for(int i=0;i<a;i++){
LL xa,ya;
scanf("%lld%lld",&xa,&ya);
pax+=xa*xa;pay+=ya*ya;
sax+=xa;say+=ya;
}
LL ans= INF;
for(int i=0;i<b;i++){
LL xb,yb;
scanf("%lld%lld",&xb,&yb);
LL tx=INF;
LL bs=0;
for(LL x=sax/a-3;x<sax/a+4;x++){
LL c = a*x*x + pax - 2*sax*x + abs(x-xb);
if(c<tx)tx=c;
}
bs+=tx;
tx=INF;
for(LL y=say/a-3;y<say/a+4;y++){
LL c = a*y*y + pay - 2*say*y + abs(y-yb);
if(c<tx)tx=c;
}
bs+=tx;
if(ans>bs) ans = bs;
}
printf("Case #%d: %lld\n",ks,ans);
}
return 0;
}