HDU/杭电2013多校第二场解题报告

2024-05-04 19:58

本文主要是介绍HDU/杭电2013多校第二场解题报告,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这场一直在写1001,一直TLE。题解说的是DP,dp的用处.....

 

1001:就是变换球的位置求话费;想法太简单了,还是得用优化的算法,一直在写,一直T:

 

#include <cstdio>
#include <cstring>
#include <vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 200006
#define MAXM 2000006
int n,a,b;
int main() {int ca;scanf("%d",&ca);while(ca--){scanf("%d%d%d",&n,&a,&b);int ans=0;if(a>b)swap(a,b);if(n<=a){puts("0");}else if(n>a&&n<b){for(int i=a;i<n;i++){ans+=abs(i%a-i%b);}}else{for(int i=a;i<n;i++){ans+=abs(i%a-i%b);}}printf("%d\n",ans);}return 0;
}


自己一直搞1001,后面的是其它的队友搞的尴尬

 

Palindrome Sub-Array

就是相当于求二维的回文,多条件判断:

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;int s[305][305];
int n,m;
int l;
int ans;
void init()
{scanf("%d%d",&n,&m);for(int i=0; i<n; i++){for(int j=0; j<m; j++){scanf("%d",&s[i][j]);}}
}
void solve()
{ans = 1;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(min(n-i,m-j) <= ans){break;}l = min(n-i,m-j);while(l > ans){if(s[i][j]==s[i+l-1][j]&&s[i+l-1][j]==s[i][j+l-1]&&s[i][j+l-1]==s[i+l-1][j+l-1]){int q = 0;for(int k = 1; k * 2 < l; k++){if(s[i+k][j]==s[i+l-1-k][j]&&s[i+l-1-k][j]==s[i+k][j+l-1]&&s[i+k][j+l-1]==s[i+l-1-k][j+l-1]){if(s[i][j+k]==s[i+l-1][j+k]&&s[i+l-1][j+k]==s[i][j+l-1-k]&&s[i][j+l-1-k]==s[i+l-1][j+l-1-k]){if(s[i+k][j+k]==s[i+l-1-k][j+k]&&s[i+l-1-k][j+k]==s[i+k][j+l-1-k]&&s[i+k][j+l-1-k]==s[i+l-1-k][j+l-1-k])continue;else{q = 1;break;}}else{q = 1;break;}}else{q = 1;break;}for(int c = k - 1; c > 0; c--){if(s[i+k][j+c]==s[i+l-1-k][j+c]&&s[i+l-1-k][j+c]==s[i+k][j+l-1-c]&&s[i+k][j+l-1-c]==s[i+l-1-k][j+l-1-c]){if(s[i+c][j+k]==s[i+l-1-c][j+k]&&s[i+l-1-c][j+k]==s[i+c][j+l-1-k]&&s[i+c][j+l-1-k]==s[i+l-1-c][j+l-1-k]){continue;}else{q = 1;break;}}else{q = 1;break;}}if(q == 1)break;}if(q == 0)ans = l;}l--;}}}printf("%d\n",ans);
}
int main()
{int t;scanf("%d",&t);while(t--){init();solve();}return 0;
}

Warm up

 

#include <cstdio>
#include <cstring>
#include <vector>
#include<queue>
#include<cmath>
#include <algorithm>
using namespace std;
#define MAXN 200006
#define MAXM 2000006
#pragma comment(linker, "/STACK:1024000000,1024000000")
struct node {int v, w, pre;
} edge[MAXM];
int pos[MAXN], nEdge; //图的存储:链式前向星(池子法)struct Bridge {int u, v;
} bridge[MAXM];  //用来记录桥
int tot; //桥的个数int fa[MAXN], cc; //fa:各个点所属的缩点(连通块),cc连通块的个数
int dfn[MAXN], low[MAXN], Time; //时间戳
int stack[MAXN], top;   //用于维护连通块的
int n, m;   //点的个数和边的条数void connect(int u, int v, int w) {nEdge++;edge[nEdge].pre = pos[u];edge[nEdge].v = v;edge[nEdge].w = w;pos[u] = nEdge;
}
vector<int> graph[MAXN];
void tarjan(int cur, int from, int from_edge) {low[cur] = dfn[cur] = Time++;stack[++top] = cur;for (int p=pos[cur]; p; p=edge[p].pre) {int v = edge[p].v;if (v == from&&abs(p-from_edge)<=1) continue;  //注意一下这里if (!dfn[v]) {tarjan(v, cur, p);if (low[v] < low[cur]) low[cur] = low[v];if (low[v] > dfn[cur]) {bridge[tot].u = cur;bridge[tot++].v = v;cc++;graph[cc].clear();do {fa[stack[top]] = cc;} while (stack[top--] != v);}} else if (low[cur] > dfn[v]) low[cur] = dfn[v];}
}
int bfs(int x,int flag)
{queue<int> q;int y;q.push(x);memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));low[x]=0;dfn[x]=1;while(q.size()>0){y=q.front();//     printf("%d\n",y);q.pop();for(int i=0;i<graph[y].size();i++){int z=graph[y][i];if(!dfn[z]){dfn[z]=1;low[z]=low[y]+1;q.push(z);}}}if(flag)return y;return low[y];
}
int main() {while(scanf("%d%d", &n, &m),n+m){memset(pos, 0, sizeof(pos));nEdge = 0;int u, v, w;for (int i=0; i<m; i++) {scanf("%d%d", &u, &v);connect(u, v, 1);connect(v, u, 1);}memset(dfn, 0, sizeof(dfn));memset(fa, -1, sizeof(fa));cc = tot = 0;for (int i=1; i<=n; i++)if (!dfn[i]) {top = Time = 1;tarjan(i, -1, -3);++cc;graph[cc].clear();for (int j=1; j<=n; j++)if (dfn[j] && fa[j]==-1) fa[j] = cc;}for(int i=0;i<tot;i++){graph[fa[bridge[i].u]].push_back(fa[bridge[i].v]);graph[fa[bridge[i].v]].push_back(fa[bridge[i].u]);}int y=bfs(1,1);int ans2=bfs(y,0);//  printf("%d %d\n",cc,ans2);printf("%d\n",cc-1-(ans2));}return 0;
}

Warm up 2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;inline void RD(int &ret) {char c;do {c = getchar();} while(c < '0' || c > '9') ;ret = c - '0';while((c=getchar()) >= '0' && c <= '9')ret = ret * 10 + ( c - '0' );
}
int Map[1111][1111] ;
int link[1111] ;
bool vis[1111] ;
int n , m ,s, v;
int dfs(int now)
{for (int i = 1 ;i <= m ;i ++){if(Map[now][i])if(!vis[i]){vis[i] = 1 ;if(link[i] == -1 || dfs(link[i])){link[i] = now ;return 1 ;}}}return 0 ;
}int x1[1111], y1[1111] ;
int x2[11111],y2[1111] ;
bool check(int i , int j){if(x1[i] <= x2[j] && x2[j] <= x1[i] + 1){if(y2[j] <= y1[i] && y2[j] + 1 >= y1[i]){return 1 ;}}return 0 ;
}
int main() {while(scanf("%d%d",&n,&m) , (n +  m)){mem(Map,0) ;mem(link , -1) ;for (int i = 1 ; i <= n ;i ++ ){scanf("%d%d",&x1[i] ,&y1[i]) ;}for (int i = 1 ; i <= m ;i ++ ){scanf("%d%d",&x2[i] , &y2[i]) ;}for (int i = 1 ; i <= n ; i ++ ){for (int j = 1 ; j <= m ;j ++ ){Map[i][j] = check(i , j ) ;}}
//        for (int i = 1 ; i <= n ;i ++ ){
//            for (int j = 1 ; j <= m ;j ++ ){
//                cout << Map[i][j]<< " " ;
//            }
//            cout << endl;
//        }int ans = 0 ;for (int i = 1 ; i <= n ;i ++){mem(vis, 0 ) ;ans += dfs(i) ;}cout << n + m - ans << endl;}return 0 ;
}

今天的题目赛后数据有加强的,还得继续努力啊。1001已经TLE到跪了,请大神指点...

这篇关于HDU/杭电2013多校第二场解题报告的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/959995

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri