这场比赛赛后反应坑点很多，比如数据太弱，比如各种坑。。。。然而对自己的练习价值还是很大的
首先上个链接：2015四川省赛4436-4445
百度到的题解：点我看百度题解
先分析每个题，再来分析比赛
A：水题：每个开根号判断就好了
int main(){
//input;
while(scanf("%d",&n)!=EOF){
int flag=1;
for(int i=1;i<=n;i++){
scanf("%d",&num);
if (int(sqrt(num*1.0)*sqrt(num*1.0))!=num) flag=0;
}
if (flag) puts("Yes");
else puts("No");
}
return 0;
}B：题意：定义进位，问n个数，两两相加之后共会有多少个进位总数
脑洞数学题，拿个数举例子的话，68823：
要找尾数3的进位，要找其他数的个位大于等于7的
要找尾数23的进位，要找其他数的个位大于等于77的
要找尾数823的进位，要找其他数的个位大于等于177的
要找尾数8823的进位，要找其他数的个位大于等于1177的
要找尾数68823的进位，要找其他数的个位大于等于31177的
现在的思路已经有了，把每个数的尾数全部截出来，然后跟其他的数的同样长度的尾数进行比较，看看能不能进位。。
但是这样的时间是O（n^2）的
但是，我们用最简单的办法减小复杂度！~二分！
所以，最终的方法为，每个数截取同样长度的数位，各个数位单独从小到大查找自己所需要的“补数”，如823找大于等于177的（但是有个细节，找的时候可能会找到“自己”，待会处理），然后累加即可
上代码：（处理点为 ans - - 的代码）
vector<ll> G[20];
int x[maxn];
inline void in(int &x){
char ch;
x=0;
ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=9;i++) G[i].clear();
for(int i=1;i<=n;i++){
in(x[i]);
ll tp=10;
for(int k=1;k<=9;k++){
G[k].push_back(x[i]%tp);
tp*=10;
}
}
for(int i=1;i<=9;i++) sort(G[i].begin(),G[i].end());
ll ans=0;
for(int i=1;i<=n;i++){
ll tp=10;
for(int k=1;k<=9;k++){
ll tt=x[i]%tp;
tt=tp-tt;
int u=lower_bound(G[k].begin(),G[k].end(),tt)-G[k].begin();
ans+=G[k].size()-u;
if (tt<=x[i]%tp) ans--;
tp*=10;
}
}
printf("%lld\n",ans/2);
}
return 0;
}C题：字符串，给定A和B串，要求在B串中找到A串第一次出现的位置然后删除，将其未删除的左右两部分合并之后继续操作，问最后还剩下哪些字符
首先介绍一个伟大的算法：KMP算法
这个算法的精髓就是Next数组，因为在暴力操作中一旦匹配失败是退回到初始位置继续，而Next数组的处理之后能够退回到“”最有可能"再次匹配的地方（利用之前所有的匹配信息），弄懂了这一点，这个题就好做
然后，很明显，需要kmp_pre处理A串，然后把B串中的匹配字符串删除，未匹配的存在一个新的字符串中，仍然维护B在A中的Next数组
代码如下（特别简洁）：其中pos数组仍然代表失去匹配之后下个位置去哪儿找
void kmp_pre(char x[],int m,int Next[]){
int i=0,j;
j=Next[0]=-1;
while(i<m){
while(j!=-1&&x[i]!=x[j]) j=Next[j];
Next[++i]=++j;
}
}
int Next[N],pos[N];
char stk[N];
int KMP_Count(char x[],int m,char y[],int n){
int i,j,ip;
kmp_pre(x,m,Next);
i=j=ip=0;
while(ip<n){
stk[i]=y[ip++];
while(j!=-1&&stk[i]!=x[j]) j=Next[j];
i++;j++;
pos[i]=j;
if (j>=m){
i-=m;
j=pos[i];
}
}
return i;
}
char pat[N],src[N];
int main(){
while(scanf("%s%s",pat,src)==2){
int l=KMP_Count(pat,strlen(pat),src,strlen(src));
stk[l]='\0';
puts(stk);
}
return 0;
}
D题：最小点覆盖
弱用二分图匹配水过，，，然而并不能正确的，但是弱弱在这贴个板子
int uN,vN;
int g[maxn][maxn];
int linker[maxn];
bool used[maxn];
bool dfs(int u){
for(int v=1;v<=vN;v++)
if (g[u][v]&&!used[v]){
used[v]=true;
if (linker[v]==-1||dfs(linker[v])){
linker[v]=u;
return true;
}
}
return false;
}
int hungary(){
int res=0;
memset(linker,-1,sizeof(linker));
for(int u=1;u<=uN;u++){
memset(used,false,sizeof(used));
if (dfs(u)) res++;
}
return res;
}
int main(){
//input;
int n,m,u,v;
while(scanf("%d%d",&n,&m)!=EOF){
memset(g,0,sizeof(g));
while(m--){
scanf("%d%d",&u,&v);
g[u][v]=g[v][u]=1;
}
uN=vN=n;
printf("%d\n",hungary()/2);
}
return 0;
}在赛后复制了一份巨巨的代码供大家学习暴力的优美姿势：
vector<int> adjs[MAXN];
int last[510];
bool mat[MAXN][MAXN], vis[MAXN];
int n, m;
int res;
bool mustselect(int u) {
for(int i = 0; i < u; ++i)
if(!vis[i] && mat[i][u]) return true;
return false;
}
void dfs(int u, int c) {
if(c >= res) return ;
if(u == n) {
res = c;
} else {
vis[u] = true;
dfs(u + 1, c + 1);
vis[u] = false;
if(!mustselect(u)) {
int t = 0;
foreach(it, adjs[u]) if(last[*it] == -1) {
last[*it] = u;
t++;
}
dfs(u + 1, c + t);
foreach(it, adjs[u]) if(last[*it] == u)
last[*it] = -1;
}
}
}
int solve() {
memset(vis, 0, sizeof(vis));
res = n;
dfs(0, 0);
return res;
}
int main() {
while(scanf("%d%d", &n, &m) != EOF) {
memset(mat, 0, sizeof(mat));
memset(last, -1, sizeof(last));
for(int i = 0; i < 30; ++i)
adjs[i].clear();
for(int i = 0, a, b; i < m; ++i) {
scanf("%d%d", &a, &b);
a--, b--;
if(a > b) swap(a, b);
if(b < 30) mat[a][b] = mat[b][a] = true;
else adjs[a].push_back(b);
}
n = min(n, 30);
printf("%d\n", solve());
}
return 0;
}
E题：完美数学题
首先可知，一个任意的长为x宽为y的矩形，如果可以放入n*m的矩形中，那么方案数为（n-x+1）（m-y+1）
现在开始分析：由于对称性，简化细节，保证n大于等于m（如果n<m的话可以swap）
那么，对x和y的限制有三条，x小于等于n，y小于等于m，2（x+y）小于等于k，可知取min（）
由于n和m的范围限制，我们可以枚举一维再做考虑，不妨枚举x
则有x的范围为1到min（n，k/2）
那么y的范围是1到min（k/2-x，m）
循环中不能对y循环，但是，发现！！y是从1开始连续的，把公式拆成（n-x+1）（m+1）-y（n-x+1）
y的变化是知道的！所以只需枚举x即可，y得到最大值就可以算出上述的值
int main(){
//input;
while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF){
ans=0;
if (n<m) swap(n,m);
for(w=1;w<=min(k/2-1,n);w++){
l=min(k/2-w,m);
r=(l+1)*l/2;
ans+=l*(n-w+1)*(m+1)-(n-w+1)*r;
}
cout<<ans<<endl;
}
return 0;
}F题：树状数组维护最大值：也是下载了一份巨巨的代码
思路：枚举10000这个数据点，然后用树状数组维护终点为i的最大的和（左边求一个，右边求一个），再枚举切断点取最大值即可
int lowbit(int x){
return x&(-x);
}
void modify(int x,int val){
while(x){
tree[x]=max(tree[x],val);
x-=lowbit(x);
}
}
int query(int x){
int res=0;
while(x<=m){
res=max(res,tree[x]);
x+=lowbit(x);
}
return res;
}
void init(int n){
memset(tree,0,sizeof(tree));
lmax[0]=0;
for(int i=1;i<=n;i++){
if (a[i]==0||a[i]==m) lmax[i]=lmax[i-1];
else{
lmax[i]=a[i]+query(a[i]);
modify(a[i],lmax[i]);
lmax[i]=max(lmax[i],lmax[i-1]);
}
}
memset(tree,0,sizeof(tree));
rmax[n+1]=0;
for(int i=n;i>0;i--){
if (a[i]==0||a[i]==m) rmax[i]=rmax[i+1];
else{
rmax[i]=a[i]+query(a[i]);
modify(a[i],rmax[i]);
rmax[i]=max(rmax[i],rmax[i+1]);
}
}
}
int solve(){
int res=0;
for(int i=0;i<n;i++)
if (b[i]==m){
for(int j=1;j<n;j++) a[j]=b[(i+j)%n];
init(n-1);
res=max(res,max(lmax[1],rmax[n-1]));
for(int i=1;i<n-1;i++)
res=max(res,lmax[i]+rmax[i+1]);
}
return res+m;
}
int main(){
//input;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++) scanf("%d",&b[i]);
printf("%d\n",solve());
}
return 0;
}G和H弱弱不会。。。。。。。。。。
I题：坑广搜（暴力还是保平安啊。。。。。）
题意：给定n点完全图，其中m条边长度为a，剩下的所有边长度都为b，求1到n的最短路径
这个题的最大难度不是思路，而是数据量：n最大100000，所以存数据不能用矩阵，跑算法不能O（n^2）
弱比赛的时候没过，赛后巨巨们的思路是用链表或者并查集之类的数据结构维护：当前那些点没有访问过
代码如下：
int head[MAXV], ecnt;
int to[MAXE], nxt[MAXE];
int n, m, a, b;
void init() {
memset(head + 1, -1, n * sizeof(int));
ecnt = 0;
}
void add_edge(int u, int v) {
to[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; nxt[ecnt] = head[v]; head[v] = ecnt++;
}
int dis[MAXV];
int solvea() {
fill(dis + 1, dis + n + 1, b);
dis[1] = 0;
queue<int> que; que.push(1);
while(!que.empty()) {
int u = que.front(); que.pop();
for(int p = head[u]; ~p; p = nxt[p]) {
int v = to[p];
if(dis[u] + a < dis[v]) {
dis[v] = dis[u] + a;
que.push(v);
}
}
}
return dis[n];
}
int cnt[MAXV];
int solveb() {
fill(dis + 1, dis + n + 1, a);
dis[1] = 0;
priority_queue<pair<int, int> > que;
memset(cnt + 1, 0, n * sizeof(int));
for(int p = head[1]; ~p; p = nxt[p])
cnt[to[p]]++;
for(int i = 2; i <= n; ++i)
que.push(make_pair(-cnt[i], i));
int viscnt = 1, d = b;
while(!que.empty() && d < a) {
int upper = viscnt;
while(!que.empty() && -que.top().first < upper) {
int c = -que.top().first, u = que.top().second; que.pop();
if(cnt[u] != c) continue;
viscnt++;
dis[u] = d;
for(int p = head[u]; ~p; p = nxt[p]) {
int v = to[p];
if(dis[v] == a && cnt[v] < upper) {
cnt[v]++;
que.push(make_pair(-cnt[v], v));
}
}
}
d += b;
if(viscnt == upper) break;
}
return dis[n];
}
int main() {
while(scanf("%d%d%d%d", &n, &m, &a, &b) != EOF) {
init();
for(int i = 0, u, v; i < m; ++i) {
scanf("%d%d", &u, &v);
add_edge(u, v);
}
if(a < b) printf("%d\n", solvea());
if(a == b) printf("%d\n", a);
if(a > b) printf("%d\n", solveb());
}
}
J题：暴力枚举题
从（0，0）开始，根据题意，暴力找石头看看会不会撞到，如果会，找一个最近的提前转弯
注意细节点：（1）最大值不够大，在比较点的时候会WA（2）4种方向的最大最小不同，而且求最近
struct NODE
{
int x,y;
int tow;
int vis[4];
}node[2000];
int main(){
//input;
int i,j,k,l,t,n,ans;
while(scanf("%d",&n)!=EOF){
memset(node,0,sizeof(node));
for(i=1;i<=n;i++)
scanf("%d%d",&node[i].x,&node[i].y);
NODE now;
now.tow=0;
now.x=now.y=0;
ans=0;
while(1){
t=0;
int mini=INF,maxi=-INF;
if(now.tow==0){
for(i=1;i<=n;i++){
if(node[i].y==now.y&&node[i].x>now.x&&mini>node[i].x){
mini=node[i].x; t=i;
}
}
if(t!=0) now.x=node[t].x-1;
}
if(now.tow==1){
for(i=1;i<=n;i++){
if(node[i].x==now.x&&node[i].y<now.y&&maxi<node[i].y){
maxi=node[i].y; t=i;
}
}
if(t!=0) now.y=node[t].y+1;
}
if(now.tow==2){
for(i=1;i<=n;i++){
if(node[i].y==now.y&&node[i].x<now.x&&maxi<node[i].x){
maxi=node[i].x; t=i;
}
}
if(t!=0) now.x=node[t].x+1;
}
if(now.tow==3){
for(i=1;i<=n;i++){
if(node[i].x==now.x&&node[i].y>now.y&&mini>node[i].y){
mini=node[i].y; t=i;
}
}
if(t!=0) now.y=node[t].y-1;
}
if(t==0){
cout<<ans<<endl;
break;
}
else if(node[t].vis[now.tow]==1){
cout<<-1<<endl; break;
}
else{
ans++;
node[t].vis[now.tow]=1;
now.tow=(now.tow+1)%4;
}
}
}
return 0;
}谢谢xdlove巨巨和y761823巨巨的赛后分享代码和思路
————————————————————————————————————————————————————————
今天，中国篮球又让我找到了自己的兴奋点！明天加油！
京公网安备 11010502036488号