BestCoder Round 70

时间:2022-03-28 05:28:30

惨败,不能再嘲笑别人了,否则自己也会像别人那样倒霉

HDU 5615:http://acm.hdu.edu.cn/showproblem.php?pid=5615

求ax^2+bx+c能否拆成(px+k)(qx+m)的形式

不错的方法,原来的被hack了

 #include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm> #define rep(i,a,n) for(int i = a;i < n;i++)
#define per(i,n,a) for(int i = n-1;i >=a;i--)
#define pb push_back
#define VI vector<int>
#define QI queue<int>
#define log2(N) log10(N)/log10(2)
#define eps 1e-8 typedef long long ll; using namespace std; int main(){
int T;
scanf("%d",&T);
while(T--){
ll a,b,c,d;
scanf("%I64d%I64d%I64d",&a,&b,&c);
d = b*b - *a*c;
if(d == (ll)sqrt(d)*(ll)sqrt(d)){
puts("YES");
}
else{
puts("NO");
}
}
return ;
}

HDU 5616:http://acm.hdu.edu.cn/showproblem.php?pid=5616

01背包,记得要来回两次

另外为了简便用到了操作符或 0|0 = 0, 0|1 = 1, 1|1 = 1

 #include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm> #define rep(i,a,n) for(int i = a;i < n;i++)
#define per(i,n,a) for(int i = n-1;i >=a;i--)
#define pb push_back
#define VI vector<int>
#define QI queue<int>
#define log2(N) log10(N)/log10(2)
#define eps 1e-8 typedef long long ll; using namespace std; const int N = + ;
const int MAXN = + ;
int n,sum;
int a[N] = {};
int dp[MAXN] = {}; int main(){
int T;
scanf("%d",&T);
while(T--){
sum = ;
scanf("%d",&n);
rep(i,,n){
scanf("%d",&a[i]);
sum += a[i];
}
memset(dp,,sizeof(dp));
dp[] = ;
rep(i,,n){
per(j,sum+,a[i]){
dp[j] |= dp[j-a[i]];
}
}
rep(i,,n){
rep(j,,sum-a[i]+){
dp[j] |= dp[j+a[i]];
}
}
int z;
scanf("%d",&z);
while(z--){
int s;
scanf("%d",&s);
if(dp[s]){
printf("YES\n");
}
else{
printf("NO\n");
}
}
}
return ;
}

HDU 5617:http://acm.hdu.edu.cn/showproblem.php?pid=5617

学习的是NANOAPE的代码。赶紧记录一下。

写得还是糊里糊涂,希望牛人能再指导一下。

 #include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm> #define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define pb push_back
#define VI vector<int>
#define QI queue<int>
#define log2(N) log10(N)/log10(2)
#define eps 1e-8 typedef long long ll; using namespace std; const int MOD = ;
const int MAXN = + ;
char s[MAXN][MAXN] = {};
int n;
int dp[][MAXN][MAXN] = {}; //第一个表示状态,第二个表示j横坐标,第三个表示k横坐标 int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(i,,n-){
scanf("%s",s+i); //s+i相当于s[i]
}
memset(dp,,sizeof(dp));
if(s[][] != s[n-][n-]){ //如果左上角第一个和右下角最后一个不一样,直接输出0
puts("");
continue;
}
dp[][][n] = ; //先让起点和终点为1
rep(i,,n){
int a = i& ;int b = - a; //可以产生两种状态,0和1
rep(j,,i){
per(k,n,n-i){
if(s[j-][i-j+-] == s[k-][n-(i-(n-k))+-]){ //这步非常关键,估计也看的出来是在比较是否两个字母相同。其中n-(i-(n-k))最难理解,大牛写得更是看不懂,如果是我自己的话这样写就能推理出来了吧^_^
dp[a][j][k] = (dp[b][j][k]+dp[b][j-][k]+dp[b][j][k+]+dp[b][j-][k+])%MOD; //分别把前后坐标时候的总数给加起来
}
else{
dp[a][j][k] = ;
}
}
}
} int ans = ;
rep(i,,n){
(ans += dp[n&][i][i])%=MOD; //假设分别是从两头开始出发的,当他们的横坐标都是i且相遇的时候的总数
}
printf("%d\n",ans);
}
return ;
}