A——HDU 5974 A Simple Math Problem <-题目链接 签到题
Given two positive integers a and b,find suitable X and Y to meet the conditions:X+Y=aLeast Common Multiple (X, Y) =b
Input
Input includes multiple sets of test data.Each test data occupies one line,including two positive integers a(1≤a≤2*10^4),b(1≤b≤10^9),and their meanings are shown in the description.Contains most of the 12W test cases.
Output
For each set of input data,output a line of two integers,representing X, Y.If you cannot find such X and Y,output one line of "No Solution"(without quotation).
Sample Input
6 8 798 10780
Sample Output
No Solution 308 490
这里需要知道一个神奇的结论：
和一个普通的结论：
神奇的结论证明可以：
设;
然后就证明了QAQ
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<ctime>
#define up(i,x,y) for(int i = x;i <= y;i ++)
#define down(i,x,y) for(int i = x;i >= y;i --)
#define mem(a,b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define lson p<<1
#define rson p<<1|1
using namespace std;
typedef long long ll;
const int INF = 2147483640;
const double eps = 1e-8;
const int size = 1010;
const ll mod = 1e9+7;inline void RD(int &x)
{x = 0; char c; c = getchar();bool flag = 0;if(c == '-') flag = 1;while(c < '0' || c > '9') {if(c == '-') {flag = 1;} c = getchar();}while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0',c = getchar();
}
ll gcd(ll a,ll b){return b == 0 ? a : gcd(b,a%b);}ll a,b;
int main()
{while(scanf("%lld%lld",&a,&b) == 2){ll gc = gcd(a,b);ll del = a*a-4*gc*b;if(del < 0){puts("No Solution");continue;}ll sqdel = sqrt(del);if(sqdel*sqdel != del){puts("No Solution");continue;}ll ans1 = (a + (ll)sqdel);ll ans2 = (a - (ll)sqdel);if(ans1 > 0 && ans1 % 2 == 0 && ans1/2 <= a){ll ou1 = ans1/2;ll ou2 = a-ans1/2;if(ou1 > ou2) swap(ou1,ou2);printf("%lld %lld\n",ou1,ou2);}else if(ans2 > 0 && ans2 % 2 == 0 && ans2/2 <= a){ll ou1 = ans2/2;ll ou2 = a-ans2/2;if(ou1 > ou2) swap(ou1,ou2);printf("%lld %lld\n",ou1,ou2);}else{puts("No Solution");}}return 0;
}F - Binary Strings <-题目链接 铜牌题
Gym - 101845B
题目大意：给定两个长度相同的01串，同时定义两种操作：
操作1：把当前字符串最后一位移到第一位
操作2：翻转两个相邻的串
求进行最小的操作2次的数来把第一个变成第二个串，如果无法转化输出-1，如果可以输出操作2进行的次数
数据范围支持暴力，不过尽管能暴力还是要注意一个问题，第一个和最后一个也是可以交换的。
为什么？通过题意来看是不可以的，不过我们可以这样想，我先把最后一个字符移到第一位，把首位两个字符翻转,然后其他都不动，再进行操作1变成原来的位置顺序，就实现了交换。
所以暴力枚举所有可能的操作1的情况，然后每种情况暴力判断可不可以转换过去，如果可以就取ans = min(ans,nowcnt)，否则不操作.
代码很简单：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<ctime>
#define up(i,x,y) for(int i = x;i <= y;i ++)
#define down(i,x,y) for(int i = x;i >= y;i --)
#define mem(a,b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define lson p<<1
#define rson p<<1|1
#define shuchu(a) printf("qaq : %d",a);
using namespace std;
typedef long long ll;
const int INF = 2147483640;
const double eps = 1e-8;
const int SIZE = 100010;
const ll mod = 1e9+7;inline void RD(int &x)
{x = 0; char c; c = getchar();bool flag = 0;if(c == '-') flag = 1;while(c < '0' || c > '9') {if(c == '-') {flag = 1;} c = getchar();}while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0',c = getchar();
}char s1[SIZE],s2[SIZE],s3[SIZE];
int len;
void routate()
{char c = s1[len];down(i,len-1,1) s1[i+1] = s1[i];s1[1] = c;return ;
}
int ans = INF;
void check()
{int tot = 0;up(i,1,len) s3[i] = s1[i];down(i,len,2){if(s3[i] != s2[i]){if(s3[i] == '1') s3[i] = '0';else s3[i] = '1';if(s3[i-1] == '1') s3[i-1] = '0';else s3[i-1] = '1';tot ++;}}if(s3[1] == s2[1]) ans = min(ans,tot);//tot = 0;up(i,1,len) s3[i] = s1[i];if(s3[1] == '1') s3[1] = '0';else s3[1] = '1';if(s3[len] == '1') s3[len] = '0';else s3[len] = '1';tot ++;down(i,len,2){if(s3[i] != s2[i]){if(s3[i] == '1') s3[i] = '0';else s3[i] = '1';if(s3[i-1] == '1') s3[i-1] = '0';else s3[i-1] = '1';tot ++;}}if(s3[1] == s2[1]) ans = min(ans,tot);return ;
}
int main()
{scanf("%s",s1+1);scanf("%s",s2+1);len = strlen(s1+1);up(i,len+1,len*2) s1[i] = s1[i - len];up(st,1,len){//st为起点routate();check();}if(ans == INF) printf("-1\n");else printf("%d\n",ans);return 0;
}
/*
10110
11111
*/
G - Cryptography<-题目链接 签到题
Gym - 101845C
送分题。
题意很好读，不再赘述。
因为字符从33开始，32是空格 所以scanf%s读即可。
方法1：前向星建图，每个字母跑一遍spfa(),顺便记忆化一下。
方法2：大部分人都这么做的，弗洛伊德暴力n^3跑一遍任意两点最短路，但是，细节，细节，细节！
两点间可能给出多条边！！如果用邻接矩阵，一定要取最小值！！
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<ctime>
#define up(i,x,y) for(int i = x;i <= y;i ++)
#define down(i,x,y) for(int i = x;i >= y;i --)
#define mem(a,b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define lson p<<1
#define rson p<<1|1
using namespace std;
typedef long long ll;
const int INF = 500000010;
const double eps = 1e-8;
const int size = 100010;
const ll mod = 1e9+7;int dist[150][150];
int minn = INF,maxx = -1;
char s1[size],s2[size];
void flo()
{up(k,minn,maxx){up(i,minn,maxx){up(j,minn,maxx){if(dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);}}}
}
int n;
int main()
{
// for(char i = 33;i <= 126;i ++) cout<<(int)i<<" : "<<i<<endl;
// cout<<(int)' '<<endl;{gets(s1);gets(s2);up(i,0,149){up(j,0,149){dist[i][j] = INF;}}up(i,0,149) dist[i][i] = 0;// printf("%s\n%s",s1,s2);scanf("%d",&n);getchar();up(i,1,n){char a,b;int c;cin>>a>>b>>c;// cout<<a<<b<<c<<endl;dist[a][b] = min(dist[a][b],c);//！！！！！！！！！！！！！！！ minn = min(minn,min((int)a,(int)b));maxx = max(maxx,max((int)a,(int)b));}flo();ll ans = 0;int l = strlen(s1);up(i,0,l-1){ if(s1[i] == s2[i]) continue;// printf("%d\n",dist[s1[i]][s2[i]]);if(dist[s1[i]][s2[i]] == INF){ans = -1;break;}ans += (ll)dist[s1[i]][s2[i]];}printf("%I64d\n",ans);}return 0;
}
/*
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
1
a b 30000000
*/H - The Intriguing Obsession<-题目链接 铜牌题
CodeForces - 869C
参考博客：在这里
附图：
顺便 三棱柱是左边这东西 不是右边这东西23333333333
考场上没想出来确实值得自己反思一下
题解博客说的很好了，我就不多说了。有一个小技巧下一个题介绍
I - Anton and School - 2 <-题目链接 银牌题
CodeForces - 785D
题目大意：给定一个括号序列，问有多少种()或者(())这种完整的包裹的括号子序列，不能是()()这种
思路：队友做的，膜大佬
我们想一个有左括号的地方，假设它左边有a个( 右边有b个)
那么这个点对答案的贡献是：......
（解释一下 代表只选当前左括号，从右边右边右括号中选一个 ）
（代表从当前位置左边左括号选一个，从右边右括号里选两个）
然后所有合法的值得和就是它这个位置对答案的贡献
然后，你以为这样就完了吗233
然后咋整啊= = ——进入挂机模式zzz
队友无聊翻书：卧槽！！！你猜我找到了什么！！！！
史上最刺激AC题目
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<ctime>
#define up(i,x,y) for(int i = x;i <= y;i ++)
#define down(i,x,y) for(int i = x;i >= y;i --)
#define mem(a,b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define lson p<<1
#define rson p<<1|1
using namespace std;
typedef long long ll;
const int INF = 2147483640;
const double eps = 1e-8;
const int SIZE = 200010;
const ll mod = 1000000007;inline void RD(int &x)
{x = 0; char c; c = getchar();bool flag = 0;if(c == '-') flag = 1;while(c < '0' || c > '9') {if(c == '-') {flag = 1;} c = getchar();}while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0',c = getchar();
}
int l[SIZE],r[SIZE];//左边有几个左括号 右边有几个右括号
char s[SIZE];
ll inv[SIZE];
ll facinv[SIZE],fac[SIZE];//逆元阶乘表 阶乘表
void init()
{fac[0] = facinv[0] = 1;inv[1]=1; for(int i = 2; i <= 200000; i++) inv[i]=(mod-mod/i) * inv[mod%i] % mod;facinv[1] = inv[1];for(int i = 2; i <= 200000; i++) facinv[i] = facinv[i-1] * inv[i] % mod;fac[1] = 1;for(int i = 2; i <= 200000; i++) fac[i] = fac[i-1] * i % mod;
}ll C(ll a,ll b)
{return ((fac[a] * facinv[b])%mod * facinv[a-b])%mod;
}int main()
{init();scanf("%s",s);int len = strlen(s);l[0] = (s[0] == '(' );up(i,1,len-1){l[i] = l[i-1] + (s[i] == '(' );// printf("%d : %d\n",i,l[i]);}r[len-1] = s[len-1] == ')';down(i,len-2,0) r[i] = r[i+1] + (s[i] == ')' );ll ans = 0;up(i,0,len-1){if(s[i] == '(' ){// printf("l,r : %d %d\n",l[i],r[i]);ans = (ans + C(l[i]-1+r[i],r[i]-1))%mod;// printf("ans : %d\n",ans);}}printf("%I64d\n",ans);return 0;
}
J - Purifying Machine<-题目链接 铜牌题
POJ - 2724
题目大意：自己百度2333
思路：强行把每个带*的都拆开。
然后对每个数再拆成两个，如果一个数可以通过改变二进制的某一位变成另一个数，比如a,b两个点，然后a->b^1和b->a^1建边
然后这就是个二分图了，相当于求最大边覆盖，通过定理我们知道就是求最大匹配。
但是，我为什么wr了一上午+半个下午呢？
我们来看这个最大匹配，模拟样例我们可以看出来匹配一般是一对一对的匹配。所以最后要除以2
但是，其实……有匹配数为奇数的时候。。这个时候答案加的就是匹配数/2+1了，因为那个单独的1无法成对匹配。
所以最终答案要分一下类（也可以不用分类，直接ans += pipei/2 + pipei%2;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<ctime>
#define up(i,x,y) for(int i = x;i <= y;i ++)
#define down(i,x,y) for(int i = x;i >= y;i --)
#define mem(a,b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define lson p<<1
#define rson p<<1|1
using namespace std;
typedef long long ll;
const int INF = 2147483640;
const double eps = 1e-8;
const int SIZE = 23330;
const ll mod = 1e9+7;struct Edge{int to;}edges[SIZE];
int head[SIZE],next[SIZE],tot;
void build(int f,int t)
{edges[++tot].to = t;next[tot] = head[f];head[f] = tot;
}
bool vis[SIZE];
int connect[SIZE];
int bian;
bool dfs(int u)
{for(int i = head[u];i;i = next[i]){int v = edges[i].to;if(!vis[v]){vis[v] = 1;if(!connect[v] || dfs(connect[v])){connect[v] = u;return true;}}}return false;
}
char s[SIZE];
int num[SIZE];
bool quchong[SIZE];
int cnt,n,m;
void init()
{mem(edges,0);mem(head,0);mem(next,0);tot = 0;mem(connect,0);bian = 0;//二分图最大边覆盖 mem(num,0);mem(quchong,0);cnt = 0;//数的个数 mem(vis,0);
}
bool check(int x,int y)
{int dif = 0; for(int i = 0;i <= 11;i ++){int a = (1 << i);if((x&a) != (y&a)) dif ++;if(dif > 1) break; }if(dif == 1) return true;return false;
}
int main()
{freopen("case.txt","r",stdin);freopen("wode.txt","w",stdout);while(scanf("%d%d",&n,&m) && n && m){init();up(i,1,m){scanf("\n%s",s);int a = 0,b = -1;bool flag = 0;up(j,0,n-1){if(s[j] == '*'){b = a;a = (a << 1) + 1;b = (b << 1);flag = 1;}else{a = ((a << 1) | (s[j] - '0'));if(flag) b = ((b << 1) | (s[j] - '0'));}}if(!quchong[a]){num[cnt ++] = a;quchong[a] = 1;}if(b != -1 && !quchong[b]){num[cnt ++] = b;//从零开始 quchong[b] = 1;}}// printf("cnt : %d\n",cnt); // printf("%d %d %d %d\n",num[0],num[1],num[2],num[3]);up(i,0,cnt-1){up(j,0,cnt-1){if(i == j) continue ;int a = num[i];int b = num[j];if(check(a,b)){// printf("i,j : %d %d\n",i,j);build(i,j*2+1);}}}for(int i = 0;i < cnt;i ++){memset(vis,0,sizeof(vis));if(dfs(i)) bian ++;}// printf("bian : %d\n",bian); printf("%d\n",bian/2 + bian%2 + (cnt - bian));}return 0;
}/*
3 6
*01
100
011
1*1
110
001
0 01 2
1
0
0 03 3
1*1
100
011*/其他题暂时没看，目测D,K还是可做的题，都是银牌题左右的题把。
