T1 Problème de criblage par intervalle
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int prime[N];
ll values[N];//pour [L, R]
bool not_prime[N];
ll left, right;
void sieve(int size){
for(int i = 2; i <= size; ++i){
if(!not_prime[i]) prime[++prime[0]] = i;
for(int j = 1; j <= prime[0] && i * prime[j] <= size; ++j){
not_prime[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
for(int i = 1; i <= prime[0]; ++i){
for(ll j = ceil(1.0 * left/prime[i]); j <= floor(1.0 * right/prime[i]); ++j){
assert(j * prime[i] >= left && j * prime[i] <= right);
if(!values[j * prime[i] - left + 1]) values[j * prime[i] - left+1] = prime[i];
}
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> left >> right;
sieve(1e6 + 5);
for(int i = 1; i<= right -left + 1; ++i){
if(!values[i]) values[i] = i + left - 1;
cout <<values[i] <<"\n";
}
return 0;
}
T2 Simulation simple, mais un point a été raté : lors de la restauration, on n'a pas utilisé la valeur originale mais 0 100->70
#include<bits/stdc++.h>
using namespace std;
const int N = 15, Q = 100 + 10, L = 50;
enum{acc = 1, err_spa, err_row, err_col, err_sqr};
typedef pair<int, int> pii;
vector<pii> blk[N];
int belong[N][N];
int n = 9;
struct t_block{
int data[N][N];
static bool legal(int x){
return 1 <= x && x <= 9;
}
int check_simp(int x, int y, int p){
bool vis[N] = {};
if(legal(data[x][y])) return err_spa;
data[x][y] = p;
for(int i = 1; i <= n; ++i){
if(!legal(data[x][i])) continue;
if(vis[data[x][i]]) return err_row;
vis[data[x][i]] = true;
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i){
if(!legal(data[i][y])) continue;
if(vis[data[i][y]]) return err_col;
vis[data[i][y]] = true;
}
memset(vis, 0, sizeof(vis));
for(auto plc : blk[belong[x][y]]){
if(!legal(data[plc.first][plc.second])) continue;
if(vis[data[plc.first][plc.second]]) return err_sqr;
vis[data[plc.first][plc.second]] = true;
}
return acc;
}
int check(int x, int y, int p){
int rw = data[x][y];
int ret = check_simp(x, y, p);
data[x][y] = rw;
return ret;
}
int insert(int x, int y, int p){
int ret = check(x, y, p);
if(ret != acc) return ret;
data[x][y] = p;
return acc;
}
int del(int x, int y){
if(!legal(data[x][y])) return err_spa;
data[x][y] = 0;
return acc;
}
vector<int> query(int x, int y){
vector<int> ret;
if(data[x][y]) return {-1};
for(int i = 1; i <= 9; ++i){
if(check(x, y, i) == acc) ret.push_back(i);
}
return ret;
}
const int* operator[](int x)const{
return data[x];
}
pii merge(const t_block & a, const t_block& b){
int ret1 = 0, ret2 = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(a[i][j] && check(i, j, a[i][j])){
++ret1;
data[i][j] = a[i][j];
}else if(b[i][j] && check(i, j, b[i][j])){
++ret2;
data[i][j] = b[i][j];
}
}
}
return {ret1, ret2};
}
void showline(){
for(int i = 1; i <= 9; i) cout <<"+-";
cout <<"+\n";
}
void show(){
for(int i = 1; i <= n; ++i){
showline();
for(int j = 1; j <= n; ++j){
cout <<"|" << data[i][j];
}
cout <<"|"<<"\n";
}
showline();
}
void input(){
char str[L];
for(int i = 1; i <= n; ++i){
cin >> (str + 1);
cin >> (str + 1);
for(int j = 1; j <= n; ++j){
data[i][j] = str[j * 2] -'0';
}
}
cin >> (str + 1);
}
}block[Q];
int main(){
for(int i = 1; i <= 9; ++i){
for(int j = 1; j <= 9; ++j){
belong[i][j] = ceil(1.0 * i / 3) * 3 + ceil(1.0 * j / 3);
}
}
for(int i = 1; i <= 9; ++i){
for(int j = 1; j <= 9; ++j){
blk[belong[i][j]].emplace_back(i, j);
}
}
block[0].input();
int q;
cin >> q;
for(int i = 1; i <= q; ++i){
char opt[L];
cin >> (opt + 1);
if(opt[1] == 'I'){
block[i] = block[i-1];
int x, y, p;
cin >> x >> y >> p;
int ret = block[i].insert(x, y, p);
switch(ret){
case acc: cout <<"OK!"<<"\n";break;
case err_spa: cout<<"Error!"<<"\n";break;
case err_row: cout <<"Error:row!"<<"\n";break;
case err_col: cout<<"Error:column!"<<"\n";break;
case err_sqr: cout<<"Error:square!"<<"\n";break;
default: abort();
}
}else if(opt[1] == 'D'){
int x, y;
cin >> x >> y;
block[i] = block[i-1];
int ret = block[i].del(x, y);
if(ret == err_spa){
cout <<"Error!"<<"\n";
}else if(ret == acc){
cout<<"OK!"<<"\n";
}else abort();
}else if(opt[1] =='Q'){
int x, y;
cin >> x >> y;
block[i] = block[i-1];
vector<int> p = block[i].query(x, y);
if(p.size() == 1 && p[0] == -1){
cout <<"Error!"<<"\n";
}else{
cout << p.size() <<"\n";
for(int j : p){
cout << j <<"\n";
}
}
}else if(opt[1] =='M'){
int a, b;
cin >> a >> b;
pii res = block[i].merge(block[a], block[b]);
cout << res.first <<" " << res.second <<"\n";
}else if(opt[1] == 'P'){
block[i] = block[i-1];
block[i].show();
}
}
return 0;
}
T3 Problème basé sur une conclusion, l'idée est d'attribuer à la première ligne une matrice A et à la deuxième ligne une matrice B, puis le résultat est le maximum du chemin Z dans le coin supérieur gauche au coin inférieur droit. La condition de permutation est transitive, doncc on peut trier directement.
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct student{
int a, b;
bool operator <(const student& rhs)const{
return min(a, rhs.b) < min(rhs.a, b);
}
}s[N];
ll c[N];
int n;
ll get_answer(){
ll res = 0;
c[1] = s[1].a + s[1].b;
ll sum_a = s[1].a;
for(int i = 2; i <= n; ++i){
sum_a += s[i].a;
c[i] = max(c[i-1], sum_a) + s[i].b;
}
for(int i = 1; i <= n; ++i){
res = max(res, c[i]);
}
return res;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> s[i].a >> s[i].b;
sort(s + 1, s + 1 + n);
cout << get_answer() <<"\n";
}
int main(){
int T;
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> T;
while(T--){
solve();
}
return 0;
}
T4 Première partie : calcul de probabiilté, problème avec le format de sortie : 50->10 Deuxième partie : problème similaire à dp de chiffres Soit $f(x)$ le nombre d'opérations pour obtenir la valeur maximale après un XOR avec $x$ On observe que, en considérant d'abord le bit le plus haut, si $x$ est rempli de 1, alors $f(x)$ est rempli de 0, et ensuite les autres bits sont tous remplis de 1, ce qui permet de calculer directement Dans ce cas, $x$ n'est pas limité, mais $f(x)$ est limité, nous effectuons dfs uniqueemnt pour cette situation Si $n-1$ est égal à $1$, alors lorsque $x=0$, $f(x)=1$, et lorsque $x=1$, $f(x)=0$ Pour la première situation, $f(x)$ est toujours limité, nous effectuons dfs directement, pour la seconde situation, aucun n'est limité, nous calculons directement Si $n-1$ est égal à $0$, alors $f(x)$ doit être $0$ et limité, nous continuons donc le dfs Attention aux erreurs de précision avec log
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ld> pdd;//probabilité
ll n;ld p;
ll get_count(int d){
ll res1 = floor(1.0 * (n + 1) / (1ll << (d +1))) *(1ll << d);
ll res2 = ((n+1) % (1ll << (d + 1))) - (1ll << (d));
return res1 + max(res2, 0ll);
}
const ld eps =1e-10;
ld mabs(ld x){
return x > 0? x : -x;
}
ld equal(ld x, ld y){
return mabs(x-y) <= eps;
}
void print(ld x){
if(equal(x, 0)){
assert(0);
cout<<fixed<<setprecision(5) << x <<" " << 0 << endl;
return;
}
int bits = log10(x);
x = x * pow(10, -bits);
cout<<fixed<<setprecision(5) << x <<" " << bits << endl;
}
ll getpos(int x){
return (n >> x) & 1;
}
ld dfs(int pos, bool lim){//limite f(x)
if(pos < 0) return 0;
ld res = 0;
if(lim){//premier bit, limite x, aussi limite f(x)
if(getpos(pos) == 1){
//choisir 1, f(x) choisir 0, puis f(x) non limité
res = res + 1.0 * (((n) &((1ll << pos) - 1)) + 1) / (n + 1) * ((1ll << (pos + 1)) -1);
//choisir 0, f(x) choisir 1
res = res + 1.0 * (1ll << (pos)) / (n + 1) * (1ll << pos);
res = res + dfs(pos - 1, false);//x non limité, mais f(x) limité
}
else res=dfs(pos-1,1);
}else{//seulement limite f(x)
if(getpos(pos) == 1){
//remplir 1, f(x) remplit 0, puis rien n'est limité
res = res + 1.0 * (1ll << pos) / (n + 1)* ((1ll << (pos + 1) )- 1);
//remplir 0, f(x) remplit 1, puis f(x) limité
res = res + 1.0 *(1ll << pos) / (n + 1)* (1ll << pos);
res = res + dfs(pos - 1, false);
}else{
//x remplir 1 ou 0, f(x) ne peut remplir que 0, et reste limité
//remplir 1 apporte une contribution
res = res + 1.0 * (1ll << pos) /(n + 1) *(1ll << pos) + 2 * dfs(pos-1, false);
}
}
return res;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> p;
cerr<<n << " " << p << endl;
--n;
int b = floor(log2(n));
ld ans1 = 0, ans2 = 0;
for(int i = 0; i <= b; ++i){
ld prob = 1.0 * get_count(i) / (n+1);
ld dt = 2 * prob *(1 - prob)* (1ll << i);
ans2 = ans2 + dt;
}
ans1 = dfs(b, true);
cerr<<"ans1 = "<<ans1 <<" ans2 = " <<ans2 << endl;
ld ans = ans1 * p + ans2 * (1 - p);
print(ans);
return 0;
}