A - Middle of the Contest
这没什么好说的了吧......
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=505;
int main()
{
int h1,m1;
scanf("%d:%d",&h1,&m1);
int h2,m2;
scanf("%d:%d",&h2,&m2);
int tot1=h1*60+m1;
int tot2=h2*60+m2;
if(tot1>tot2)
swap(tot1,tot2);
int sub=(tot2-tot1)/2;
int ans=tot1+sub;
int h_ans=ans/60;
int m_ans=ans%60;
printf("%02d:%02d\n",h_ans,m_ans);
return 0;
}B - Preparation for International Women's Day
这题有必要说一下。首先对于两个数a,b，若要它们的和可以整除k，则有以下两种情况: * 1.a%k == 0且b%k == 0 * 2.(a%k+b%k)%k == 0
做法是，首先用一个arr数组把输入的所有数%k的结果存起来，数组里面存的是余数所出现的次数。对于第一种情况，只需要用arr[0]去处理。而对于0以外的余数，则将arr[i]和arr[k-i]进行比较。若arr[i]！=arr[k-i],则ans+=min(arr[i],arr[k-i]);若arr[i]==arr[k-i],则ans+=arr[i](或者ans+=arr[k-i])。还需要考虑一种情况，如果i==k-i，则ans+=arr[i]。另外，还需要注意，如果arr[i]==arr[k-i]与i==k-i同时成立，很明显应该ans+=arr[i]。
代码如下：
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=105;
int arr[maxn];
int main()
{
int n,k;
mst(arr,0);
cin>>n>>k;
for(int i=0;i<n;i++){
int tmp;
cin>>tmp;
arr[tmp%k]++;
}
int ans=0;
ans+=arr[0]/2;
for(int i=1;i<=k/2;i++){
if(arr[i]!=arr[k-i]){
ans+=min(arr[i],arr[k-i]);
}else if(i==k-i){ //<-1
ans+=arr[i]/2;
}else if(arr[i]==arr[k-i]){ //<-2
ans+=arr[i];
}
//1和2不能颠倒，因为如果两者都成立，则应该执行1
}
printf("%d\n",ans*2);
return 0;
}先排个序，然后对于学生i，二分找出第一个比a[i]+5大的数的下标，然后以此维护最大值
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
int a[maxn<<1];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
int pos;
sort(a,a+n);
int ans=-1;int t1;
for(int i=0;i<n;i++){
int tmp=a[i]+5;
pos=upper_bound(a,a+n,tmp)-a;
ans=max(ans,pos-i);
}
cout<<ans<<endl;
}D - Zero Quantity Maximization
用map记录每一个d出现的次数，然后再找出value值最大的d。要注意的是,当a==0&&b==0时，d一定存在且为任意实数，故ans++；当a==0&&b!=0时，无解，直接跳过。昨晚TLE了好几发居然是因为数组开小了OTZ
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
double a[2*maxn];
map<long double,int> mp;
int main()
{
int n;
cin>>n;
int ans=0;
for(int i=0;i<n;i++)
cin>>a[i];
int ok=0;
for(int i=0;i<n;i++){
long double b;
cin>>b;
if(b==0&&a[i]==0){
ok++;
continue;
}
if(b!=0&&a[i]==0){
continue;
}
long double tmp=(-b)/a[i];
mp[tmp]++;
}
map<long double,int>::iterator it;
for(it=mp.begin();it!=mp.end();it++)
ans=max(ans,it->second);
printf("%d\n",ans+ok);
return 0;
}C题的升级版。一开始是用的贪心，然后就wa了......正确方法是dp，但我不会OTZ......遂看题解。
首先当然是排个序
然后，状态转移方程是这个👇
dp[i][j]指的是前i个人组成j个队伍最多可以挑选多少人；pos是i左侧第一个满足 arr[i]-arr[pos]的点的下标。
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=5005;
int arr[maxn];
int dp[maxn][maxn];
bool cmp(int a,int b)
{
return a>b;
}
//dp[i][j]=max(dp[i-1][j],dp[pos-1][j-1]+i-pos+1)
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>arr[i];
sort(arr+1,arr+1+n);
mst(dp,0);dp[0][0]=0;
int pos=1;
for(int i=1;i<=n;i++){
pos=1;
while(arr[i]-arr[pos]>5&&pos<=n) pos++;
for(int j=1;j<=min(k,i);j++)
dp[i][j]=max(dp[i-1][j],dp[pos-1][j-1]+i-pos+1);
}
int ans=-1;
for(int i=1;i<=k;i++)
ans=max(ans,dp[n][i]);
cout<<ans<<endl;
}