比赛链接：“山大地纬杯”第十二届山东省ICPC大学生程序设计竞赛(正式赛）
首先看了眼榜单，过的比较多的是A题，所以目标也就在了A题。
A题：A Seventeen
一开始想要通过逆推，先全部加起来再减去目标十七，剩下的和和每个数的二倍比较，如果大，就减去这个数，反之则加。
#include<bits/stdc++.h>
using namespace std;
int a[55];
int main(){
int n;
cin>>n;
if(n<=3)cout<<"-1";
else if(n==4)cout<<"(2+4)*3-1";
else if(n==5)cout<<"(3*5+4-2)*1";
else {
memset(a,0,sizeof(0));
int res=0;
for(int i=1;i<=n;i++)res+=i;
res-=17;
for(int i=n;i>=1;i--){
if(res>=i*2){
a[i]=-1;
res-=i*2;
}
}
for(int i=1;i<=n;i++){
if(a[i]==0) {
a[i]=-2;break;
}
}
for(int i=1;i<=n;i++){
if(a[i]==-1)cout<<'-';
else if(a[i]==0)cout<<'+';
cout<<i;
}
}
return 0;
}
上交了两发后发现这种方法，在对于所有数的和数的和是偶数时有用，但是奇数则不行。再分类讨论也觉得麻烦，终于发现这题和周期有关，例如8-9-10+11为零，可以先写出四种初始情况，再往后四个四个加就行，交了两发终于过了。
#include<bits/stdc++.h>
using namespace std;
int a[55];
int main(){
int n;
cin>>n;
if(n<=3){
cout<<"-1";return 0;
}
else if(n%4==0){
cout<<"(2+4)*3-1";
}
else if(n%4==1){
cout<<"(3*5+4-2)*1";
}
else if(n%4==2){
cout<<"1-2+3+4+5+6";
}
else {
cout<<"7+6-5+4+3+2*1";
}
for(int i=n%4+5;i<=n;i+=4){
printf("-%d+%d+%d-%d",i,i+1,i+2,i+3);
}
return 0;
}
然后看了B题，发现可以写但是代码量比较大，于是根据榜单选择了K题
K题：K Coins
一开始认为可以通过贪心每次对于最大硬币取余，但经过讨论发现，12=5+7，但是12如果拿了11就没法再拿了；
但是又提出：可以把所有数包括两个数三个数四个数的加和也加进数列，再枚举，但是发现还得记录组合的硬币数和比较，比较麻烦；
又说可以用dp解决，方便稳定，于是有了：
#include<bits/stdc++.h>
using namespace std;
int dpa[500],dpb[500];
const int maxn=1000000000;
int main()
{
int q,x;
cin>>q;
memset(dpa,127,sizeof(dpa));
memset(dpb,127,sizeof(dpb));
dpa[0]=0;dpa[2]=1;dpa[3]=1;dpa[17]=1;dpa[19]=1;
for(int i=3;i<=19*19;i++){
if(i-2>0)dpa[i]=min(dpa[i],dpa[i-2]+1);
if(i-3>0)dpa[i]=min(dpa[i],dpa[i-3]+1);
if(i-17>0)dpa[i]=min(dpa[i],dpa[i-17]+1);
if(i-19>0)dpa[i]=min(dpa[i],dpa[i-19]+1);
}
dpb[0]=0;dpb[5]=1;dpb[7]=1;dpb[11]=1;dpb[13]=1;
for(int i=5;i<=13*13;i++){
if(i-5>0)dpb[i]=min(dpb[i],dpb[i-5]+1);
if(i-7>0)dpb[i]=min(dpb[i],dpb[i-7]+1);
if(i-11>0)dpb[i]=min(dpb[i],dpb[i-11]+1);
if(i-13>0)dpb[i]=min(dpb[i],dpb[i-13]+1);
}
//cout<<dpa[6];
while(q--)
{
cin>>x;
if(x==0)cout<<"both";
else if(dpa[x%(19*19)]+19*(x/(19*19))>maxn&&dpb[x%(13*13)]+13*(x/(13*13))>maxn)cout<<"-1";
else if(dpa[x%(19*19)]+19*(x/(19*19))>maxn||dpa[x%(19*19)]+19*(x/(19*19))>dpb[x%(13*13)]+13*(x/(13*13)))cout<<'B';
else if(dpb[x%(13*13)]+13*(x/(13*13))>maxn||dpa[x%(19*19)]+19*(x/(19*19))<dpb[x%(13*13)]+13*(x/(13*13)))cout<<'A';
else if(dpa[x%(19*19)]+19*(x/(19*19))==dpb[x%(13*13)]+13*(x/(13*13)))cout<<"both";
printf("\n");
}
return 0;
}
但是没有过，是和一开始一样的问题，没有考虑12=5+7的问题，于是准备算准时间限制扩大dp范围，试了试果然过了：
#include<bits/stdc++.h>
using namespace std;
int dpa[10000005],dpb[10000005];
const int maxn=1000000000;
int main()
{
int q,x;
cin>>q;
memset(dpa,127,sizeof(dpa));
memset(dpb,127,sizeof(dpb));
dpa[0]=0;dpa[2]=1;dpa[3]=1;dpa[17]=1;dpa[19]=1;
for(int i=3;i<=10000000;i++){
if(i-2>0)dpa[i]=min(dpa[i],dpa[i-2]+1);
if(i-3>0)dpa[i]=min(dpa[i],dpa[i-3]+1);
if(i-17>0)dpa[i]=min(dpa[i],dpa[i-17]+1);
if(i-19>0)dpa[i]=min(dpa[i],dpa[i-19]+1);
}
dpb[0]=0;dpb[5]=1;dpb[7]=1;dpb[11]=1;dpb[13]=1;
for(int i=5;i<=10000000;i++){
if(i-5>0)dpb[i]=min(dpb[i],dpb[i-5]+1);
if(i-7>0)dpb[i]=min(dpb[i],dpb[i-7]+1);
if(i-11>0)dpb[i]=min(dpb[i],dpb[i-11]+1);
if(i-13>0)dpb[i]=min(dpb[i],dpb[i-13]+1);
}
//cout<<dpa[6];
while(q--)
{
cin>>x;
if(x==0)cout<<"both";
else if(x>=10000000)cout<<'A';
else if(dpa[x]>maxn&&dpb[x]>maxn)cout<<"-1";
else if(dpa[x]>maxn||dpa[x]>dpb[x])cout<<'B';
else if(dpb[x]>maxn||dpa[x]<dpb[x])cout<<'A';
else if(dpa[x]==dpb[x])cout<<"both";
printf("\n");
}
return 0;
}
看了眼榜单来到H题：H Counting
在这题卡住了，一直超时
?
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 3e3 + 10,M = 3e3+ 10;
int T,n,m,k;
map<PII,int>ma[M];
char s[N][N];
struct pi{
int x,y;
}q[N];
int main(){
scanf("%d%d%d%d",&n,&m,&k,&T);
for(int i = 1;i <= k;i ++){
scanf("%d%d",&q[i].x,&q[i].y);
ma[0][{q[i].x,q[i].y}] ++;
}
getchar();
for(int i = 1;i <= k;i ++){
for(int j = 0;j < T ;j ++)
{
scanf("%c",&s[i][j]);
}
getchar();
}
LL res = 0;
for(auto item:ma[0]){
res += item.second * (item.second - 1) * 2;
}
printf("%lld\n",res);
for(int l = 0;l < T;l ++)
{
LL ans = 0;
for(int i=1;i <= k;i ++){
int dx= 0,dy= 0;
if(s[i][l] == 'L')dy = -1;
else if(s[i][l] == 'R') dy = 1;
else if(s[i][l] == 'U') dx = -1;
else dx = 1;
q[i].x += dx;
q[i].y += dy;
//PII temp = {q[i].x,q[i].y};
PII temp = {q[i].x,q[i].y};
if(ma[l + 1][temp] > 0){
ans += (ma[l + 1][temp] + 1) * ma[l + 1][temp] / 2;
ans -= (ma[l + 1][temp] - 1) * ma[l + 1][temp] / 2;
}
ma[l + 1][temp] ++;
}
printf("%lld\n",ans);
}
return 0;
}
被数据卡住了，就差一点可以不超时，也是算法的问题，没能优化出来
赛后看别人的代码并补题：
#include <cstdio>
#define N 2010
#define T 3010
int n, m, k, t;
int count[N][N];
int pos[N][2];
char movements[N][T];
long long sum;
void move(int &x, int &y, char move) {
switch (move) {
case 'L':
y -= 1;
break;
case 'R':
y += 1;
break;
case 'U':
x -= 1;
break;
case 'D':
x += 1;
break;
}
}
int main() {
scanf("%d %d %d %d", &n, &m, &k, &t);
for (int i = 0; i < k; i++) {
scanf("%d %d", &pos[i][0], &pos[i][1]);
int &c = count[pos[i][0]][pos[i][1]];
if (c > 1) {
sum -= c * (c - 1) / 2;
}
c++;
if (c > 1) {
sum += c * (c - 1) / 2;
}
}
for (int i = 0; i < k; i++) {
scanf("%s", movements[i]);
}
printf("%d\n", sum);
for (int i = 0; i < t; i++) {
for (int j = 0; j < k; j++) {
int &c = count[pos[j][0]][pos[j][1]];
if (c > 1) {
sum -= c * (c - 1) / 2;
}
c--;
if (c > 1) {
sum += c * (c - 1) / 2;
}
move(pos[j][0], pos[j][1], movements[j][i]);
int &c1 = count[pos[j][0]][pos[j][1]];
if (c1 > 1) {
sum -= c1 * (c1 - 1) / 2;
}
c1++;
if (c1 > 1) {
sum += c1 * (c1 - 1) / 2;
}
}
printf("%d\n", sum);
}
return 0;
}
以为这次比赛被H题卡住没有牌子了，但是却卡到了cu尾，庆幸之余更多的是反思与汲取教训。
