因为rating不够QAQ就报了Div2。。
[CA Loves Stick]
CA喜欢玩木棍。
有一天他获得了四根木棍，他想知道用这些木棍能不能拼成一个四边形。
Sample Input
2
1 1 1 1
1 1 9 2
Sample Output
Yes
No
CE的心塞啊。。居然没有<bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream> using namespace std; typedef unsigned long long ll;
ll a[4];
int main(){
int test;
scanf("%d", &test);
while(test --){
for(int i = 0; i < 4; i ++)
cin >> a[i];
sort(a, a+4);
bool flag = true;
for(int i = 0; i < 4; i ++)
if(a[i] == 0){
flag = false;
break;
}
if(flag == false || a[3] - a[2] >= a[0] + a[1])
puts("No");
else puts("Yes");
}
return 0;
}
[CA Loves GCD]
问题描述
CA喜欢是一个热爱党和人民的优秀同♂志，所以他也非常喜欢GCD（请在输入法中输入GCD得到CA喜欢GCD的原因）。
现在他有N个不同的数，每次他会从中选出若干个（至少一个数），求出所有数的GCD然后放回去。
为了使自己不会无聊，CA会把每种不同的选法都选一遍，CA想知道他得到的所有GCD的和是多少。
我们认为两种选法不同，当且仅当有一个数在其中一种选法中被选中了，而在另外一种选法中没有被选中。
输入样例
2
2
2 4
3
1 2 3
输出样例
8
10
枚举因子，容斥，还是蛮简单的。。(也不知道是谁调了很久都没调出来)
可以做到O(nlogn).然而手残写的O(n^2)
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 1010
using namespace std;
typedef long long ll;
#define mod 100000007 int a[maxn], n; ll ans[maxn], pow2[maxn]; int main(){
int test;
scanf("%d", &test);
pow2[0] = 1;
for(int i = 1; i <= 1000; i ++)
pow2[i] = (pow2[i-1] << 1) % mod;
while(test --){
scanf("%d", &n);
int mx = 0;
for(int i = 1; i <= n; i ++)
scanf("%d", &a[i]), mx = max(mx, a[i]);
sort(a+1, a+1+n);
memset(ans, 0, sizeof ans);
for(int i = 1; i <= mx; i ++){
int cnt = 0;
for(int j = 1; j <= n; j ++)
cnt += a[j] % i == 0;
ans[i] = pow2[cnt] - 1;
} for(int i = mx; i; i --)
for(int j = i + i; j <= mx; j += i)
ans[i] -= ans[j], ans[i] %= mod; ll ret = 0;
for(int i = 1; i <= mx; i ++)
ret += 1ll * ans[i] * i, ret %= mod; printf("%I64d\n", (ret + mod) % mod);
}
return 0;
}
[CA Loves Palindromic]
CA喜欢字符串，尤其喜欢回文串。
有一天他得到一个字符串，他想知道子串中有多少回文子串，本质相同位置不同的算一种。每次给个区间[l, r]
然后就是PAM。。枚举l暴力构建PAM。。
因为len<=1000还蛮小的QAQ
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 2010
using namespace std; int n, s[maxn]; char str[maxn]; struct Node{
int fail, nxt[26], len;
void clear(){
memset(nxt, 0, sizeof nxt);
len = fail = 0;
}
}st[maxn]; int last, size, len; void init(){
last = len = 0;
st[0].clear(), st[1].clear();
st[0].len = 0, st[1].len = -1;
st[0].fail = st[1].fail = 1;
s[0] = -1; size = 1;
} int get_fail(int x){
while(s[len-st[x].len-1] != s[len])
x = st[x].fail;
return x;
} int sz[maxn]; void Extend(int c){
s[++ len] = c;
int cur = get_fail(last);
if(!st[cur].nxt[c]){
int now = ++ size;st[now].clear();
st[now].len = st[cur].len + 2;
st[now].fail = st[get_fail(st[cur].fail)].nxt[c];
st[cur].nxt[c] = now;
}
last = st[cur].nxt[c];
} int ans[maxn][maxn]; void solve(){
for(int i = 1; i <= n; i ++){
init();
for(int j = i; j <= n; j ++){
Extend(str[j]-'a');
ans[i][j] = size - 1;
}
}
} void read(int& num){
char ch = getchar(); num = 0;
for(; ch < '!'; ch = getchar());
for(; ch > '!'; ch = getchar())
num = (num << 1) + (num << 3) + (ch ^ 48);
} int main(){
int test;
scanf("%d", &test);
while(test --){
init();
scanf("%s", str+1);
n = strlen(str+1);
solve();
int Q, l, r;
read(Q);
for(int i = 1; i <= Q; i ++){
read(l), read(r);
printf("%d\n", ans[l][r]);
}
} return 0;
}