招行信用卡中心开发编程题解
还挺晚的..20:30才开始
选择题分很多而且几乎不会，Java，sql啥的...凉了一大半..
3个编程，有点codeforce题目的感觉，看着觉得难，其实没什么厉害的算法就是不好想。
第一题给一串LR组成的字符串，每个位置一个机器人，每个机器人在L就往左走1步在R就往右1步。问10^100步后每个格子有几个机器人。保证最左的格子是R最右的格子是L。
10^100挺吓人的..其实知道这是一个很大的偶数就可以。
发现每个机器人必定走入一个LR或RL循环，所以只要记录：当前位置左边的第一个R和当前位置右边的第一个L，就知道机器人在哪个循环里。
然后判断一下奇偶，就知道最后机器人在循环里的L还是R。线性过3遍，复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
char ss[100005];
int l[100005];
int r[100005];
int ans[100005];
int main()
{
int i, j;
int n;
while (~scanf("%s", ss))
{
n = strlen(ss);
for (i = 0; i < n; i++)
if (ss[i] == 'R')
r[i] = i;
else
r[i] = r[i - 1];
for (i = n - 1; i >= 0; i--)
if (ss[i] == 'L')
l[i] = i;
else
l[i] = l[i + 1];
for (i = 0; i < n; i++)
{
int count;
if (ss[i] == 'R')
{
count = l[i] - i;
if (count % 2 == 0)
ans[l[i]]++;
else
ans[l[i] - 1]++;
}
else//L
{
count = i - r[i];
if (count % 2 == 0)
ans[r[i]]++;
else
ans[r[i] + 1]++;
}
}
printf("%d",ans[0]);
for (i = 1; i < n; i++)
printf(" %d", ans[i]);
puts("");
}
return 0;
} 第二题给一个树，1是根节点，有边权，可能是负数，求什么来着..好像是求每个点构成的子树里，从根出发最长的路径（可以没有路径，所以至少是0）节点数20W
求的啥记不清了，反正dp的是dp[当前节点]=max(dp[子节点]+路径权)，遍历一遍树就行
重点是存边的方式吧..用的acm里的方法，链表vector那种存也行，别二维数组..
好多人这题没过..不太记得有啥要点了..别开N*N的二维数组..存双向边，存答案用longlong..
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct { int v, w, ne; }a[200005 << 1];
int h[200005];
int k;
int vi[200005];
LL ans[200005];
void add(int u, int v, int w)//初始k=1
{
a[k].v = v, a[k].w = w, a[k].ne = h[u], h[u] = k++;
}
LL dfs(int u)
{
if (vi[u] == 1)
return ans[u];
vi[u] = 1;
for (int i = h[u]; i; i = a[i].ne)
{
LL temp = a[i].w;
if (vi[a[i].v] == 0)
ans[u] = max(ans[u], temp + dfs(a[i].v));
}
return ans[u];
}
int main()
{
int i, j;
int n;
while (~scanf("%d", &n))
{
k = 1;
for (i = 1; i < n; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
printf("%lld", dfs(1));
for (i = 2; i <= n; i++)
printf(" %lld",dfs(i));
puts("");
}
return 0;
} 第三个，给一个数字和？构成的字符串，？可以填0-9，求有几种可能让填成的数%13=5，允许有前导0，答案%1e9+7
以为是数论排列组合啥的，想了好久，其实dp一下就行..
思想是记录当前位之前构成的串%13的13种值的个数，后面加一个数字，就是a*10+b这种的转移，对取模也是一样的。
转移方程就是dp1[(10*j+k)%13]+=dp0[j]。dp0是先前的数组，dp1是空的，新的数组。j取0到12，k取当前数位，？就取0-9。（滚动数组节约内存，但没必要..）
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL mm = 1000000007;
char ss[100005];
LL dp0[15], dp1[15];
int main()
{
int i, j, k;
int n;
while (~scanf("%s", ss))
{
n = strlen(ss);
memset(dp0, 0, sizeof(dp0));
memset(dp1, 0, sizeof(dp1));
if (ss[0] == '?')
for (i = 0; i < 10; i++)
dp0[i] = 1;
else
dp0[ss[0] - '0'] = 1;
for (i = 1; i < n; i++)
{
for (j = 0; j < 13; j++)
{
if (ss[i] == '?')
for (k = 0; k < 10; k++)
{
dp1[(10 * j + k) % 13] += dp0[j];
dp1[(10 * j + k) % 13] %= mm;
}
else
{
dp1[(10 * j + ss[i] - '0') % 13] += dp0[j];
dp1[(10 * j + ss[i] - '0') % 13] %= mm;
}
}
memcpy(dp0, dp1, sizeof(dp0));
memset(dp1, 0, sizeof(dp1));
}
printf("%lld\n",dp0[5]);
}
return 0;
} 
投递兆芯等公司10个岗位 >
美团公司氛围 1905人发布
