盲打
签到题
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
const int N = 1e7 + 10,mod = 1e11 + 3;
//typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
char g[5][20] =
{
{'q','w','e','r','t','y','u','i','o','p'},
{'a','s','d','f','g','h','j','k','l',' '},
{'!','z','x','c','v','b','n','m',' ',' '}
};
void solve()
{
string s;cin >> s;
for(int i = 0; i < s.size(); i ++)
{
if(s[i] >= 'A' && s[i] <= 'Z')
{
s[i] += 'a' - 'A';
cout << 3 << " " << 1 << " ";
for(int j = 0; j < 3; j ++)
for(int k = 0; k < 10; k ++)
if(s[i] == g[j][k]){
cout << j + 1 << ' ' << k + 1 << endl;
break;
}
}
else
{
for(int j = 0; j < 3; j ++)
for(int k = 0; k < 10; k ++)
if(s[i] == g[j][k]){
cout << j + 1 << ' ' << k + 1 << endl;
break;
}
}
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
数列求和
签到题
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
const int N = 1e7 + 10,mod = 1e11 + 3;
//typedef long long LL;
#define endl "\n"
void solve()
{
int n;cin >> n;
int sum = 0;
if(n == 1)cout << 1 << endl;
else if(n == 2)cout << 4 << endl;
else
{
int a = 1,b = 3,c;
for(int i = 3; i <= n; i ++)
{
c = (a + b) % mod;
sum = (sum + c) % mod;
a = b,b = c;
}
printf("%lld\n",(sum + 4) % mod);
}
}
signed main()
{
//ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
设x为一合数,那么有x=a^k * b^p * ...,约数个数为(k+1)*(p+1)*...
我们想让这几个数的乘积为5,只有让x=a^4才能成立,其中a是质数
所以我们可以处理出1到1000之内的质数,然后暴力枚举看那些在l到r内
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
const int N = 1001,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int primes[N],cnt;
bool st[N];
void solve()
{
for(int i = 2; i < N; i ++)
{
if(!st[i])primes[cnt ++] = i;
for(int j = 0; i * primes[j] < N; j ++)
{
st[i * primes[j]] = true;
//i是pj的倍数了就退出
if(i % primes[j] == 0)break;
}
}
int T;cin >> T;
while(T --)
{
int l,r;cin >> l >> r;
int res = 0;
for(int i = 0; i < cnt; i ++)
{
int t = primes[i] * primes[i] * primes[i] * primes[i];
if(t >= l && t <= r)res ++;
}
cout << res << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
Nim游戏是所有的异或和为0先手必输,我们只能从第一堆中移动,所以可以枚举移到那一堆
只要得到所有的异或和为0那么就可以使得后手必胜了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#define int long long
const int N = 1010,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];
void solve()
{
int n;cin >> n;
int sum = 0;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
sum ^= a[i];
}
int t = sum;
for(int i = 0; i < a[1]; i ++)//枚举从第一堆中移多少
{
for(int j = 2; j <= n ; j ++)//枚举移动到那一堆中
{
sum = sum ^ a[1] ^ (a[1] - i) ^ a[j] ^ (a[j] + i);
if(sum == 0){
cout << i << endl;
return;
}
sum = t;
}
}
cout << -1 << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#define int long long
const int N = 1010,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second
void solve()
{
int x1,y1,x2,y2;
double k,x;
cin >> x1 >> x2 >> y1 >> y2;
k = (y2 - y1) * 1.0 / (x2 - x1);
x = (x1 * y1 + x2 * y2) / (k * (x1 + x2) + y1 + y2);
printf("%lf %lf",x,k * x);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
大胆猜测考察的应该是求字符串的循环节,kmp的经典应用,只要能除尽就说明合法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#define int long long
const int N = 2e6 + 10,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second
char p[N];
int ne[N];
void solve()
{
int n;cin >> n;
cin >> p + 1;
for(int i = 2,j = 0; i <= n; i ++)
{
while(j && p[i] != p[j + 1])j = ne[j];
if(p[j + 1] == p[i])j ++;
ne[i] = j;
}
int k = n - ne[n];
if(n % k)cout << 1 << endl;
else cout << n / k << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
看到数据范围我们可以想到采用二分,而且数越大越更劣,具有单调性
问题的难点是如何统计出某一段区间内0的个数,采用枚举的方式一定会超时的
我们对0进行分类讨论:
考虑对于每一位分别计算有多少数字这一位上有多少个0,令第i位上的数字是now,比第i位更高的数字组成a(上界),比第i位低的数字组成b(上界)
假设当前位位i,高位上的数可以取的值为[1,a],低位上的数可以取得的值为[0,10^i)
1.如果当前位上不是0,那么高位上可以取[1,a],低位上可以取[0,10^i),(这样低位不受高位影响了)方案数为a*10^i
2.如果当前位上是0,
(1)如果高位上的数字取[1,a),则低位数字随便取.方案数为(a-1)*10^i
(2)如果高位上的数字为a,那么低位上只能取到b.方案数为1*(b+1)
如此我们就可以用log的时间求出方案数了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
const int N = 20,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second
int f[N];
int n,k;
int quick(int x,int i)
{
return f[i];
}
int ask(int x)
{
int a = x / 10,b = 0,now = x % 10,res = 1;//将0加进去
for(int i = 0; a; i ++)//枚举每位
{
if(now != 0)
res = res + a * quick(10,i);
else res = res + (a - 1) * quick(10, i) + b + 1;
now = a % 10;
a /= 10;
b = b + x % 10 * quick(10,i);
x /= 10;
}
return res;
}
bool check(int x)
{
if(ask(n) - ask(x - 1) >= k)return true;
return false;
}
void solve()
{
cin >> n >> k;
f[0] = 1;
for(int i = 1; i <= 18; i ++)
f[i] = f[i - 1] * 10;
if(ask(n) < k)cout << -1 << endl;
else
{
int l = 0,r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid))l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
性质:a是b的祖先的充分必要条件是a点的入栈时间早于b点且a点的出栈时间晚于b点
首先必要性是显然成立的
充分性也是显然的,祖先一定也满足入栈时间早并且出栈时间晚于b,否则他们就没有在同一分支中
则有本条性质成立
因此我们只需要求出每个点的进栈时间和出栈时间,然后在b中查找是否有满足条件的存在即可
当然我们可以写lca的板子,但是要知道一个结论:求若干个点的最近公共祖先,我们只需要取这些点中dfs序最小的和最大的
两个点求lca即可
但是本题不是求最近的,只要是祖先就行,所以我们在判断一下b的祖先是否出现在a中的最近公共祖先中
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//typedef long long LL;
#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;
//typedef pair<int,int>PII;
//#define x first
//#define y second
int h[N],e[N],ne[N],idx;
int dfn[N],lfn[N],timestamp;
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void dfs(int u)
{
dfn[u] = ++ timestamp;//入栈时间
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
}
lfn[u] = ++ timestamp;//出栈时间
}
void solve()
{
int n,q;cin >> n >> q;
memset(h,-1,sizeof h);
for(int i = 2; i <= n; i ++)
{
int x;cin >> x;
add(x,i);
}
dfs(1);
while(q --)
{
int l,r;cin >> l >> r;
//cout << l << ' ' << r << endl;
int minv = INF,maxv = 0;
for(int i = 0; i < l; i ++)
{
int a;cin >> a;
minv = min(minv, dfn[a]);
maxv = max(maxv, lfn[a]);
}
bool ok = false;
for(int i = 0; i < r; i ++)
{
int a;cin >> a;
if(dfn[a] < minv && lfn[a] > maxv)
ok = true;
//注意这里不能提前退出,我们要读完所有的输入,否则会出现错误
}
if(ok)cout << "yes" << endl;
else cout << "no" << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}