B.Cuckoo for Hashing
模拟题。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define N 50007 int a[],b[]; int main()
{
int n1,n2,m,i;
int x,fx,tx;
int tmp,tmp2;
int cs = ;
while(scanf("%d%d%d",&n1,&n2,&m)!=EOF && (n1||n2||m))
{
memset(a,-,sizeof(a));
memset(b,-,sizeof(b));
while(m--)
{
scanf("%d",&x);
fx = x%n1;
tx = ;
if(a[fx] == -)
{
a[fx] = x;
continue;
}
tmp2 = x;
while(a[fx] != -)
{
tmp = a[fx];
a[fx] = tmp2;
tx = tmp%n2;
if(b[tx] != -)
{
tmp2 = b[tx];
b[tx] = tmp;
fx = tmp2%n1;
}
else
{
b[tx] = tmp;
break;
}
}
if(a[fx] == -)
a[fx] = tmp2;
}
printf("Case %d:\n",cs++);
int flag = ;
//printf("Table 1\n");
for(i=;i<n1;i++)
{
if(a[i] != -)
{
flag = ;
break;
}
}
if(flag)
{
printf("Table 1\n");
for(i=;i<n1;i++)
{
if(a[i] != -)
printf("%d:%d\n",i,a[i]);
}
}
flag = ;
for(i=;i<n2;i++)
{
if(b[i] != -)
{
flag = ;
break;
}
}
if(flag)
{
printf("Table 2\n");
for(i=;i<n2;i++)
{
if(b[i] != -)
printf("%d:%d\n",i,b[i]);
}
}
}
return ;
}
C.Playing Fair with Cryptography
模拟题，注意细节就好。遇到J的情况要及时跳走。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
#define N 50007 char mp[][];
char key[],text[];
int vis[]; string RUN(string ss)
{
int i,j;
int a,b;
int c,d;
string ans = "";
for(i=;i<;i++)
{
for(j=;j<;j++)
{
if(mp[i][j] == ss[])
a = i,b = j;
if(mp[i][j] == ss[])
c = i,d = j;
}
}
if(a == c)
{
int newb = (b+)%;
ans += mp[a][newb];
int newd = (d+)%;
ans += mp[a][newd];
return ans;
}
else if(b == d)
{
int newa = (a+)%;
ans += mp[newa][b];
int newc = (c+)%;
ans += mp[newc][b];
return ans;
}
else
{
int newb = d;
int newd = b;
ans += mp[a][newb];
ans += mp[c][newd];
return ans;
}
} int main()
{
int t,i,cs = ,j,k;
int x,y;
scanf("%d",&t);
getchar();
while(t--)
{
gets(key);
gets(text);
int len1 = strlen(text);
int len2 = strlen(key);
memset(vis,,sizeof(vis));
k = ;
for(i=;i<len2;i++)
{
char ch = key[i];
if((ch >= 'A' && ch <= 'Z'))
{
if(vis[ch-'A'])
continue;
vis[ch-'A'] = ;
mp[k/][k%] = ch;
k++;
}
else if(ch >= 'a' && ch <= 'z')
{
ch -= ;
if(vis[ch-'A'])
continue;
vis[ch-'A'] = ;
mp[k/][k%] = ch;
k++;
}
}
for(char chh = 'A';chh<='Z';chh++)
{
if(chh == 'J')
continue;
if(!vis[chh-'A'])
{
mp[k/][k%] = chh;
k++;
}
}
//alpha table established
char ss[];
k = ;
for(i=;i<len1;i++)
{
if(text[i] >= 'A' && text[i] <='Z')
ss[k++] = text[i];
else if(text[i] >= 'a' && text[i] <= 'z')
ss[k++] = text[i]-;
}
ss[k] = '\0';
printf("Case %d: ",cs++);
int nowch = ;
char nowchar;
string cy = "";
for(i=;i<k-;i+=)
{
if(nowch == )
nowch++,nowch%=;
if(ss[i] == ss[i+])
{
if(ss[i] == (nowch%) + 'A')
{
nowchar = (++nowch)% + 'A';
if(nowchar == 'J')
nowch++,nowchar = 'K';
}
nowchar = (nowch%) + 'A';
if(nowchar == 'J')
nowch++,nowchar = 'K';
cy = "";
cy += ss[i];
cy += nowchar;
cout<<RUN(cy);
nowch = (nowch+)%;
i -= ;
}
else
{
cy = "";
cy += ss[i];
cy += ss[i+];
cout<<RUN(cy);
}
}
if(i == k-)
{
nowchar = nowch% + 'A';
if(ss[i] == nowchar)
{
nowchar = (++nowch)% + 'A';
}
if(nowchar == 'J')
nowch++,nowchar = 'K';
cy = "";
cy += ss[i];
cy += nowchar;
cout<<RUN(cy);
}
cout<<endl;
}
return ;
}
H.The Urge to Merge
DP。借鉴标程代码。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#define Mod 1000000007
using namespace std;
#define N 50007 int mp[][];
ll dp[][]; ll Max(ll a,ll b,ll c,ll d)
{
return max(max(max(a,b),c),d);
} int main()
{
int cs = ,n;
int i,j,k;
while(scanf("%d",&n)!=EOF && n)
{
for(i=;i<;i++)
for(j=;j<=n;j++)
scanf("%d",&mp[i][j]);
//memset(dp,0,sizeof(dp));
for(i=;i<;i++)
dp[i][] = dp[i][] = ;
dp[][] = mp[][]*mp[][];
dp[][] = mp[][]*mp[][];
ll k1 = Max(dp[][],dp[][],,);
ll k2 = ;
ll s1,s2,s3,s4,s5; for(j=;j<=n;j++)
{
s1 = mp[][j-]*mp[][j];
s2 = mp[][j-]*mp[][j];
s3 = mp[][j-]*mp[][j];
s4 = mp[][j]*mp[][j];
s5 = mp[][j]*mp[][j]; dp[][j] = Max(k2,dp[][j-],dp[][j-],dp[][j-])+s1; //第一种组合
dp[][j] = Max(k2,dp[][j-],dp[][j-],dp[][j-])+s2; //第二种组合
dp[][j] = Max(k2,dp[][j-],dp[][j-],dp[][j-])+s3; //第三种组合 dp[][j] = Max(k2+s1+s2,dp[][j-]+s1+s2,k1+s4,);
dp[][j] = Max(k2,dp[][j-],,)+s1+s3;
dp[][j] = Max(k2+s2+s3,dp[][j-]+s2+s3,k1+s5,);
dp[][j] = Max(k2+s1+s2+s3,dp[][j]+s5,dp[][j]+s4,);
k2 = k1;
for(i=;i<;i++)
k1 = max(k1,dp[i][j]);
}
ll ans = -Mod;
for(i=;i<;i++)
ans = max(ans,dp[i][n]);
printf("Case %d: %d\n",cs++,ans);
}
return ;
}
（没做出来的以后持续更新）